<html>
<head>
<title>C++ Annotations Version 6.5.0</title>
</head>
<body text="black" bgcolor="white">
<hr>
<ul>
    <li> <a href="cplusplus.html">Table of Contents</a>
    <li> <a href="cplusplus11.html">Previous Chapter</a>
    <li> <a href="cplusplus13.html">Next Chapter</a>
</ul>
<hr>
<a name="Containers"></a><a name="l172"></a>
<h1>Chapter 12: Abstract Containers</h1>
<a name="containers"></a>
<blockquote>
    <em>
        Don't hesitate to send in feedback: send an e-mail if you like the
        C++ Annotations; if you think that important material was omitted;
        if you find errors or typos in the text or the code examples;
        or if you just feel like e-mailing. Send your e-mail to
        <a href="mailto:f.b.brokken@rug.nl">Frank B. Brokken</a>.
<p>
<strong>Please</strong> state the document version you're referring to, as found in
        the title (in this document: 6.5.0) and please state chapter and
        paragraph name or number you're referring to.
<p>
All received mail is processed conscientiously, and received
        suggestions for improvements will usually have been processed by the
        time a new version of the Annotations is released. Except for the
        incidental case I will normally not acknowledge the receipt of
        suggestions for improvements. Please don't interpret this as me not
        appreciating your efforts.
    </em>
</blockquote>
<p>
<a name="containers/container"></a><strong>C++</strong> offers several predefined datatypes, all part of the
    <a name="an1383"></a>

    <a name="an1384"></a>
 <a href="cplusplus17.html#STL">Standard Template Library</a>,
which can be used to implement solutions to frequently occurring problems. The
datatypes discussed in this chapter are all <a name="an1385"></a>
<em>containers</em>: you can put stuff
inside them, and you can retrieve the stored information from them.
<p>
The interesting part is that the kind of data that can be stored inside these
containers has been left unspecified by the time the containers were
constructed. That's why they are spoken of as <a name="an1386"></a>
<em>abstract containers</em>.
<p>
Abstract containers rely heavily on <em>templates</em>, which are covered near
the end of the <strong>C++</strong> Annotations, in chapter <a href="cplusplus18.html#TEMPLATES">18</a>. However, in
order to use the abstract containers, only a minimal grasp of the template
concept is needed. In <strong>C++</strong> a <a name="an1387"></a>
<em>template</em> is in fact a recipe for
constructing a function or a complete class. The recipe tries to abstract the
functionality of the class or function as much as possible from the data on
which the class or function operates. As the data  types on which the
templates operate were not known by the time the template was constructed, the
datatypes are either inferred from the context in which a template function is
used, or they are mentioned explicitly by the time a template class is used
(the term that's used here is <a name="an1388"></a>
<em>instantiated</em>). In situations where the
types are explicitly mentioned, the <a name="an1389"></a>
<em>angle bracket notation</em> is used to
indicate which data types are required. For example, below (in section
<a href="cplusplus12.html#PAIR">12.2</a>) we'll encounter the <a name="an1390"></a>
<code>pair</code> container, which
requires the explicit mentioning of two data types. E.g., to define a <code>pair</code>
variable containing both an <code>int</code> and a <code>string</code>, the notation
        <pre>
    pair&lt;int, string&gt; myPair;
</pre>
    is used. Here, <code>myPair</code> is defined as a <code>pair</code> variable, containing
both an <code>int</code> and a <code>string</code>.
<p>
The angle bracket notation is used intensively in the following
discussion of abstract containers. Actually, understanding this part of
templates is the only real requirement for using abstract containers. Now
that we've introduced this notation, we can postpone the more thorough
discussion of templates to chapter <a href="cplusplus18.html#TEMPLATES">18</a>, and concentrate on
their use in this chapter.
<p>
Most of the abstract containers are
    <a name="an1391"></a>
 <em>sequential</em> containers: they represent a
series of data which can be stored and retrieved in some sequential
way. Examples are the <a name="an1392"></a>
<code>vector</code>, implementing an <a name="an1393"></a>
extendable array, the
<a name="an1394"></a>
<code>list</code>, implementing a datastructure in which insertions and deletions can
be easily realized, a <a name="an1395"></a>
<code>queue</code>, also called a <a name="an1396"></a>
<em>FIFO</em>
    (<a name="an1397"></a>
first in, first out) structure, in which the first element that is
entered will be the first element that will be retrieved, and the <a name="an1398"></a>
<code>stack</code>,
which is a
    <a name="an1399"></a>
<em>first in, last out</em> (<a name="an1400"></a>
FILO or <a name="an1401"></a>
LIFO) structure.
<p>
Apart from the sequential containers, several <a name="an1402"></a>
special containers are
available. The <code>pair</code> is a basic container in which a pair of values (of
types that are left open for further specification) can be stored, like two
strings, two ints, a string and a double, etc.. Pairs are often used to return
data elements that naturally come in pairs. For example, the <a name="an1403"></a>
<code>map</code> is an
abstract container storing keys and their associated values. Elements
of these maps are returned as <code>pairs</code>.
<p>
A variant of the <code>pair</code> is the <a name="an1404"></a>
 <code>complex</code> container,
implementing operations that are defined on <a name="an1405"></a>
<em>complex numbers</em>.
<p>
All abstract containers described in this chapter and the <code>string</code> datatype
discussed in chapter <a href="cplusplus04.html#String">4</a> are part of the Standard Template
Library. There also exists an abstract container for the implementation of a
<a name="an1406"></a>
<em>hashtable</em>, but that container is not (yet) accepted by the <a name="an1407"></a>
ANSI/ISO
standard. Nevertheless, the <a href="cplusplus12.html#HASHMAP">final section</a> of this chapter will
cover the hashtable to some extent. It may be expected that containers like
<code>hash_map</code> and other, now still considered an extension, will become
part of the <a name="an1408"></a>
ANSI/ISO standard at the next release: apparently by the time
the standard was frozen these containers were not yet fully available. Now
that they are available they cannot be official part of the <strong>C++</strong> library
<a name="an1409"></a>
, but they are in fact available, albeit as extensions.
<p>
All containers support <a name="an1410"></a>

        <a name="an1411"></a>

        <a name="an1412"></a>
 the following operators:
    <ul>
    <li> The <a name="an1413"></a>
overloaded assignment operator, so we can assign two
containers of the same types to each other.
    <li> <a name="an1414"></a>
 Tests for equality: <a name="an1415"></a>
<code>==</code> and <a name="an1416"></a>
<code>!=</code>
The <a name="an1417"></a>
equality operator applied to two containers returns <a name="an1418"></a>
<code>true</code> if the two
containers have the same number of elements, which are pairwise equal
according to the equality operator of the contained data type. The
<a name="an1419"></a>
inequality operator does the opposite.
    <li> <a name="an1420"></a>
 Ordering operators: <a name="an1421"></a>
<code>&lt;</code>, <a name="an1422"></a>
<code>&lt;=</code>, <a name="an1423"></a>
<code>&gt;</code> and
<a name="an1424"></a>
<code>&gt;=</code>.  The <code>&lt;</code> operator returns <code>true</code> if each element in the
<a name="an1425"></a>
left-hand side container is less than each corresponding element in the
<a name="an1426"></a>
right-hand side container. Additional elements in either the left-hand side
container or the right-hand side container are ignored.
        <pre>
    container left;
    container right;

    left = {0, 2, 4};
    right = {1, 3};             // left &lt; right

    right = {1, 3, 6, 1, 2};    // left &lt; right
</pre>
    </ul>
    Note that <a name="an1427"></a>
 before a
user-defined type (usually a <code>class</code>-type) can be stored in a container, the
user-defined type should at least support:
    <ul>
    <li> A default-value (e.g., a <a name="an1428"></a>
default constructor)
    <li> The <a name="an1429"></a>
equality operator (<a name="an1430"></a>
<code>==</code>)
    <li> The <a name="an1431"></a>
less-than operator (<a name="an1432"></a>
<code>&lt;</code>)
    </ul>
    Closely linked to the standard template library are the
    <a name="an1433"></a>
<em>generic algorithms</em>. These algorithms may be used to perform
frequently occurring tasks or more complex tasks than is possible with the
containers themselves, like counting, filling, merging, filtering etc.. An
<a name="an1434"></a>
overview of generic algorithms and their applications is given in chapter
<a href="cplusplus17.html#STL">17</a>. Generic algorithms usually rely on the availability of
    <a name="an1435"></a>
<a href="cplusplus17.html#ITERATORS"><em>iterators</em></a>, which represent begin and
end-points for processing data stored within containers. The abstract
containers usually support constructors and members expecting iterators, and
they often have members returning iterators (comparable to the
<a name="an1436"></a>
<code>string::begin()</code> and <a name="an1437"></a>
<code>string::end()</code> members). In the remainder of this
chapter the iterator concept is not covered. Refer to chapter <a href="cplusplus17.html#STL">17</a> for
this.
<p>
The url <a name="an1438"></a>

<a target=_top href="http://www.sgi.com/Technology/STL">http://www.sgi.com/Technology/STL</a> is worth visiting by those readers
who are looking for more information about the abstract containers and the
standard template library than can be provided in the <strong>C++</strong> annotations.
<p>
Containers often collect data during their lifetimes. When a container
goes out of scope, its destructor tries to destroy its data elements. This
only succeeds if the data elements themselves are stored inside the
container. If the <a name="an1439"></a>
 data elements of containers
are pointers, the data pointed to by these pointers will not be destroyed,
resulting in a <a name="an1440"></a>
memory leak. A consequence of this scheme is that the data
stored in a container should be considered the `<a name="an1441"></a>
property' of the container:
the container should be able to destroy its data elements when the container's
destructor is called. So, normally containers should contain no pointer
data. Also, a container should not be required <a name="an1442"></a>

    <a name="an1443"></a>
 to contain <code>const</code> data, as <code>const</code> data
prevent the use of many of the container's members, like the assignment
operator.
<p>
<a name="l173"></a>
<h2>12.1: Notations used in this chapter</h2>
<a name="containers/notations"></a>    In this chapter about containers, the following
        <a name="an1444"></a>
notational convention is used:
    <ul>
    <li> Containers live in the standard namespace. In code examples this will
be clearly visible, but in the text <code>std::</code> is usually omitted.
    <li> A <a name="an1445"></a>
container without angle brackets represents any container of
that type. Mentally add the required type in
    <a name="an1446"></a>
angle bracket notation. E.g., <code>pair</code> may represent <code>pair&lt;string,
int&gt;</code>.
    <li> The notation <a name="an1447"></a>
<code>Type</code> represents the <a name="an1448"></a>
generic type. <code>Type</code> could
be <code>int</code>, <code>string</code>, etc.
    <li> Identifiers <code>object</code> and <code>container</code> represent objects of the
container type under discussion.
    <li> The identifier <code>value</code> represents a value of the type that is
stored in the container.
    <li> Simple, one-letter identifiers, like <code>n</code> represent unsigned
values.
    <li> Longer identifiers represent <a name="an1449"></a>
iterators. Examples
are <code>pos</code>, <code>from</code>, <code>beyond</code>
    </ul>
    Some containers, e.g., the <code>map</code> container, contain pairs of
values, usually called `keys' and `values'. For such containers the following
notational convention is used in addition:
    <ul>
    <li> The identifier <code>key</code> indicates a value of the used key-type
    <li> The identifier <code>keyvalue</code> indicates a value of the `<code>value_type</code>'
used with the particular container.
    </ul>
<p>
<a name="PAIR"></a><a name="l174"></a>
<h2>12.2: The `pair' container</h2>
<a name="containers/pair"></a>The <a name="an1450"></a>
 <code>pair</code> container is a rather basic container. It can
be used to store two elements, called <a name="an1451"></a>
<code>first</code> and <a name="an1452"></a>
<code>second</code>, and that's
about it. Before <code>pair</code> containers can be used the following preprocessor
directive must have been specified:
    <a name="an1453"></a>

        <pre>
    #include &lt;utility&gt;
</pre>
    The data types of a <code>pair</code> are specified when the <code>pair</code> variable is
defined (or declared), using the standard template (see chapter <code>Templates</code>)
angle bracket notation:
        <pre>
    pair&lt;string, string&gt; piper("PA28", "PH-ANI");
    pair&lt;string, string&gt; cessna("C172", "PH-ANG");
</pre>
    here, the variables <code>piper</code> and <code>cessna</code> are defined as <code>pair</code>
variables containing two <code>strings</code>. Both strings can be retrieved using the
<code>first</code> and <code>second</code> fields of the <code>pair</code> type:
        <pre>
    cout &lt;&lt; piper.first &lt;&lt; endl &lt;&lt;      // shows 'PA28'
            cessna.second &lt;&lt; endl;      // shows 'PH-ANG'
</pre>
    The <code>first</code> and <code>second</code> members can also be used to reassign values:
        <pre>
    cessna.first = "C152";
    cessna.second = "PH-ANW";
</pre>
    If a <code>pair</code> object must be completely reassigned, an <em>anonymous</em>
<a name="an1454"></a>
 pair object can be used as the <a name="an1455"></a>
right-hand operand of
the assignment. An anonymous variable defines a temporary variable (which
receives no name) solely for the purpose of (re)assigning another variable of
the same type. Its <a name="an1456"></a>
 generic form is
        <pre>
    type(initializer list)
</pre>
    Note that when a <code>pair</code> object is used the type specification is not
completed by just mentioning the containername <code>pair</code>. It also requires the
specification of the data types which are stored within the pair. For this the
(template) <a name="an1457"></a>
angle bracket notation is used again. E.g., the reassignment
of the <code>cessna</code> pair variable could have been accomplished as follows:
        <pre>
    cessna = pair&lt;string, string&gt;("C152", "PH-ANW");
</pre>
    In cases like these, the <code>type</code> specification can become quite
elaborate, which has caused a revival of interest in the possibilities offered
by the <a name="an1458"></a>
<code>typedef</code> keyword. If a lot of <a name="an1459"></a>
<code>pair&lt;type1, type2&gt;</code> clauses are
used in a source, the <a name="an1460"></a>
typing effort may be reduced and legibility might be
improved by first defining a name for the clause, and then using the defined
name later. E.g.,
        <pre>
    typedef pair&lt;string, string&gt; pairStrStr;

    cessna = pairStrStr("C152", "PH-ANW");
</pre>
    Apart from this (and the basic set of operations (assignment and
comparisons)) the <code>pair</code> offers no further <a name="an1461"></a>
functionality. It is, however,
a basic ingredient of the upcoming abstract containers <code>map, multimap</code> and
<code>hash_map</code>.
<p>
<a name="l175"></a>
<h2>12.3: Sequential Containers</h2>
<p>
<a name="l176"></a>
<h3>12.3.1: The `vector' container</h3>
    <a name="containers/vector"></a>The <a name="an1462"></a>
<code>vector</code> class implements an <a name="an1463"></a>
expandable array.
Before <code>vector</code> containers can be used the following preprocessor
directive must have been specified: <a name="an1464"></a>

        <pre>
    #include &lt;vector&gt;
</pre>
    The following constructors, operators, and member functions are available:
    <ul>
    <li> <a name="an1465"></a>
 Constructors:
        <ul>
        <li> A <code>vector</code> may be constructed empty:
        <pre>
    vector&lt;string&gt; object;
</pre>
    Note the specification of the data type to be stored in the <code>vector</code>:
the data type is given between angle brackets, just after the `<code>vector</code>'
container name. This is common practice with containers.
        <li> A vector may be initialized to a certain number of elements.  One
of the nicer characteristics of vectors (and other containers) is that it
initializes <a name="an1466"></a>
 its data elements to the data
type's <a name="an1467"></a>
default value. The data type's <a name="an1468"></a>
<em>default constructor</em> is used for
this <a name="an1469"></a>
initialization. With non-class data types the value 0 is used.  So,
for the <code>int</code> vector we know its initial values are zero.  Some examples:
        <pre>
    vector&lt;string&gt; object(5, string("Hello")); // initialize to 5 Hello's,
    vector&lt;string&gt; container(10);              // and to 10 empty strings
</pre>
        <li> A vector may be initialized using iterators. To
initialize a vector with elements 5 until 10 (including the last one) of an
existing <code>vector&lt;string&gt;</code> the following construction may be used:
        <pre>
    extern vector&lt;string&gt; container;
    vector&lt;string&gt; object(&amp;container[5], &amp;container[11]);
</pre>
    Note here that the last element pointed to by the second iterator
(<code>&amp;container[11]</code>) is <em>not</em> stored in <code>object</code>.  This is a simple
example of the use of <a name="an1470"></a>
<em>iterators</em>, in which the <a name="an1471"></a>
range of values that is
used starts at the first value, and includes all elements up to but not
including the element to which the second iterator refers. The standard
notation for this is <a name="an1472"></a>
<code>[begin, end)</code>.
        <li> A vector may be initialized using a <a name="an1473"></a>
copy constructor:
        <pre>
    extern vector&lt;string&gt; container;
    vector&lt;string&gt; object(container);
</pre>
    </ul>
    <li> In addition to the standard operators for containers, the <code>vector</code>
supports the <a name="an1474"></a>
index operator, which may be used to retrieve or reassign
individual elements of the vector. Note that the elements which are indexed
must exist. For example, having defined an empty vector a statement like
<code>ivect[0] = 18</code> produces an error, as the vector is empty.  So, the vector
is <em>not</em> automatically <a name="an1475"></a>
 expanded, and it <em>does</em>
respect its <a name="an1476"></a>
array bounds. In this case the vector should be resized first,
or <code>ivect.push_back(18)</code> should be used (see below).
    <li> The <code>vector</code> class has the following <a name="an1477"></a>

member functions:
        <ul>
        <li><a name="an1478"></a>
<code>Type &amp;vector::back()</code>:
            <blockquote>this member returns a reference to the last element in the
vector. It is the <a name="an1479"></a>
responsibility of the programmer to use the member only
if the vector is not empty.</blockquote>
        <li><a name="an1480"></a>
<code>vector::iterator vector::begin()</code>:
            <blockquote>this member returns an <a name="an1481"></a>
iterator pointing to the first
element in the vector, returning <code>vector::end()</code> if the vector is empty.</blockquote>
        <li><a name="an1482"></a>
<code>vector::clear()</code>:
            <blockquote>this member erases all the vector's elements.</blockquote>
        <li><a name="an1483"></a>
<code>bool vector::empty()</code>
            <blockquote>this member returns <code>true</code> if the vector contains no
elements.</blockquote>
        <li><a name="an1484"></a>
<code>vector::iterator vector::end()</code>:
            <blockquote>this member returns an iterator pointing beyond the last
element in the vector.</blockquote>
        <li><a name="an1485"></a>
<code>vector::iterator vector::erase()</code>:
            <blockquote>this member can be used to erase a specific range of
elements in the vector:</blockquote>
            <ul>
            <li><code>erase(pos)</code> erases the element pointed to by the iterator
<code>pos</code>. The value <code>++pos</code> is returned.
            <li><code>erase(first, beyond)</code> erases elements indicated by the iterator
range <code>[first, beyond)</code>, returning <code>beyond</code>.
            </ul>
        <li><a name="an1486"></a>
<code>Type &amp;vector::front()</code>:
            <blockquote>this member returns a reference to the first element in the
vector. It is the responsibility of the programmer to use the member only if
the vector is not empty.</blockquote>
        <li><a name="an1487"></a>
<code>... vector::insert()</code>:
            <blockquote>elements may be inserted starting at a certain position. The
return value depends on the version of <code>insert()</code> that is called:</blockquote>
            <ul>
            <li><code>vector::iterator insert(pos)</code> inserts a default value of type
<code>Type</code> at <code>pos</code>, <code>pos</code> is returned.
            <li><code>vector::iterator insert(pos, value)</code> inserts <code>value</code> at
<code>pos</code>, <code>pos</code> is returned.
            <li><code>void insert(pos, first, beyond)</code> inserts the elements in the
                <a name="an1488"></a>
iterator range <a name="an1489"></a>
<code>[first, beyond)</code>.
            <li><code>void insert(pos, n, value)</code> inserts <code>n</code> elements having value
<code>value</code> at position <code>pos</code>.
            </ul>
        <li><a name="an1490"></a>
<code>void vector::pop_back()</code>:
            <blockquote>this member removes the last element from the vector. With
an <a name="an1491"></a>
empty vector nothing happens.</blockquote>
        <li><a name="an1492"></a>
<code>void vector::push_back(value)</code>:
            <blockquote>this member adds <code>value</code> to the end of the vector.</blockquote>
        <li><a name="an1493"></a>
<code>void vector::resize()</code>:
            <blockquote>this member can be used to alter the number of elements that
are currently stored in the vector:</blockquote>
            <ul>
            <li><code>resize(n, value)</code> may be used to resize the vector to a size
of <code>n</code>. <code>Value</code> is optional. If the vector is expanded and <code>value</code> is
not provided, the additional elements are initialized to the <a name="an1494"></a>
default value
of the used data type, otherwise <code>value</code> is used to initialize extra
elements.
            </ul>
        <li><a name="an1495"></a>
<code>vector::reverse_iterator vector::rbegin()</code>:
            <blockquote><a name="an1496"></a>
 this member returns an iterator
pointing to the last element in the vector.</blockquote>
        <li><a name="an1497"></a>
<code>vector::reverse_iterator vector::rend()</code>:
            <blockquote>this member returns an iterator pointing before the first
element in the vector.</blockquote>
        <li><a name="an1498"></a>
<code>size_t vector::size()</code>
            <blockquote>this member returns the number of elements in the vector.</blockquote>
        <li><a name="an1499"></a>
<code>void vector::swap()</code>
            <blockquote>this member can be used to swap two vectors using identical
data types. E.g.,</blockquote>
        <pre>
    #include &lt;iostream&gt;
    #include &lt;vector&gt;
    using namespace std;

    int main()
    {
        vector&lt;int&gt; v1(7);
        vector&lt;int&gt; v2(10);

        v1.swap(v2);
        cout &lt;&lt; v1.size() &lt;&lt; " " &lt;&lt; v2.size() &lt;&lt; endl;
    }
    /*
        Produced output:
    10 7
    */
</pre>
        </ul>
    </ul>
<p>
<a name="l177"></a>
<h3>12.3.2: The `list' container</h3>
    <a name="containers/list"></a>The <a name="an1500"></a>
<code>list</code> container implements a <a name="an1501"></a>
list data structure.  Before <code>list</code>
containers can be used the following preprocessor directive must have been
specified: <a name="an1502"></a>

        <pre>
    #include &lt;list&gt;
</pre>
    The organization of a <code>list</code> is shown  in figure <a href="cplusplus12.html#listFig">7</a>.
        <a name="listFig"></a><p><center><img src="containers/list.gif" align="bottom" alt="Figure 7 is shown here."/><br>
Figure 7: A list data-structure
</center><p><br>

    In figure <a href="cplusplus12.html#listFig">7</a> it is shown that a list consists of separate
list-elements, connected to each other by pointers. The list can be
    <a name="an1503"></a>
 traversed in two directions: starting at <em>Front</em> the
list may be traversed from left to right, until the 0-pointer is reached at
the end of the rightmost list-element. The list can also be traversed from
right to left: starting at <em>Back</em>, the list is traversed from right to left,
until eventually the 0-pointer emanating from the leftmost list-element is
reached.
<p>
As a subtlety note that the representation given in figure <a href="cplusplus12.html#listFig">7</a> is not
necessarily used in actual implementations of the list. For example, consider
the following little program:
        <pre>
    int main()
    {
        list&lt;int&gt; l;
        cout &lt;&lt; "size: " &lt;&lt; l.size() &lt;&lt; ", first element: " &lt;&lt;
                l.front() &lt;&lt; endl;
    }
</pre>
    When this program is run it might actually produce the output:
        <pre>
    size: 0, first element: 0
</pre>
    Its front element can even be assigned a value. In this case the
implementor has choosen to insert a hidden element to the list, which is
actually a circular list, where the hidden element serves as terminating
element, replacing the 0-pointers in figure <a href="cplusplus12.html#listFig">7</a>. As noted, this is a
subtlety, which doesn't affect the conceptual notion of a list as a data
structure ending in 0-pointers. Note also that it is well known that various
implementations of list-structures are possible (cf.
    <a name="an1504"></a>
Aho, A.V., <a name="an1505"></a>
Hopcroft J.E. and <a name="an1506"></a>
Ullman, J.D., (1983)
    <a name="an1507"></a>
<em>Data Structures and Algorithms</em> (Addison-Wesley)).
<p>
Both lists and vectors are often appropriate data structures in situations
where an <a name="an1508"></a>
 unknown number of data elements must be
stored. However, there are some <a name="an1509"></a>
 rules of thumb to follow
when a choice between the two data structures must be made.
    <ul>
    <li> When the majority of accesses is <a name="an1510"></a>
random, a <code>vector</code> is
the preferred data structure. E.g., a program counting the frequencies
of characters in a textfile, a <code>vector&lt;int&gt; frequencies(256)</code> is the
datastructure doing the trick, as the values of the received characters can be
used as indices into the <code>frequencies</code> vector.
    <li> The previous example illustrates a second rule of thumb, also
favoring the <code>vector</code>: if the number of elements is known in advance (and
does not notably change during the lifetime of the program), the vector
is also preferred over the list.
    <li> In cases where <a name="an1511"></a>
insertions or <a name="an1512"></a>
deletions prevail, the list is
generally preferred. Actually, in my experience, lists aren't that useful at
all, and often an implementation will be faster when a <code>vector</code>, maybe
containing holes, is used.
    </ul>
    Other considerations related to the choice between lists and vectors
should also be given some thought. Although it is true that the vector is able
to grow dynamically, the <a name="an1513"></a>
dynamic growth does involve a lot data-copying.
Clearly, copying a million large data structures takes a considerable amount
of time, even on fast computers. On the other hand, inserting a large number
of elements in a list doesn't require us to
    <a name="an1514"></a>
copy non-involved data. Inserting a new element in a list merely
requires us to <a name="an1515"></a>
 juggle some pointers. In figure
<a href="cplusplus12.html#listAdd">8</a> this is shown: a new element is inserted between the second and
third element, creating a new list of four elements.
        <a name="listAdd"></a><p><center><img src="containers/insertlist.gif" align="bottom" alt="Figure 8 is shown here."/><br>
Figure 8: Adding a new element to a list
</center><p><br>

    Removing an element from a list also is a simple matter. Starting again
from the situation shown in figure <a href="cplusplus12.html#listFig">7</a>, figure <a href="cplusplus12.html#listDel">9</a> shows
what happens if element two is removed from our list. Again: only pointers
need to be juggled. In this case it's even simpler than adding an element:
only two pointers need to be rerouted.
        <a name="listDel"></a><p><center><img src="containers/dellist.gif" align="bottom" alt="Figure 9 is shown here."/><br>
Figure 9: Removing an element from a list
</center><p><br>

    Summarizing the comparison between lists and vectors, it's probably best
to conclude that there is no clear-cut answer to the question what data
structure to prefer. There are rules of thumb, which may be adhered to. But if
worse comes to worst, a <a name="an1516"></a>
profiler may be required to find out what's best.
<p>
But, no matter what the thoughts on the subject are, the <code>list</code>
container is available, so let's see what we can do with it.
The following constructors, operators, and member functions
are available:
    <ul>
    <li> <a name="an1517"></a>
 Constructors:
        <ul>
        <li> A <code>list</code> may be constructed empty:
        <pre>
    list&lt;string&gt; object;
</pre>
        As with the <code>vector</code>, it is an error to refer to an element of an
empty list.
        <li> A list may be initialized to a certain number of
elements. By default, if the initialization value is not explicitly mentioned,
the default value or default constructor for the actual data type is used. For
example:
        <pre>
    list&lt;string&gt; object(5, string("Hello")); // initialize to 5 Hello's
    list&lt;string&gt; container(10);              // and to 10 empty strings
</pre>
        <li> A list may be initialized using a two iterators. To
initialize a list with elements 5 until 10 (including the last one) of a
<code>vector&lt;string&gt;</code> the following construction may be used:
        <pre>
    extern vector&lt;string&gt; container;
    list&lt;string&gt; object(&amp;container[5], &amp;container[11]);
</pre>
        <li> A list may be initialized using a <a name="an1518"></a>
copy constructor:
        <pre>
    extern list&lt;string&gt; container;
    list&lt;string&gt; object(container);
</pre>
    </ul>
    <li> There are no special operators available for <code>list</code>s, apart from
the standard operators for containers.
    <li> The following <a name="an1519"></a>
member functions are available for lists:
        <ul>
        <li><a name="an1520"></a>
<code>Type &amp;list::back()</code>:<blockquote>this member returns a
reference to the last element in the list. It is the
    <a name="an1521"></a>
responsibility of the programmer to use this member only if the list is
not empty.</blockquote>
        <li><a name="an1522"></a>
<code>list::iterator list::begin()</code>:<blockquote>this member
returns an <a name="an1523"></a>
iterator pointing to the first element in the list, returning
<code>list::end()</code> if the list is empty.</blockquote>
        <li><a name="an1524"></a>
<code>list::clear()</code>:<blockquote>this member erases all elements in the list.</blockquote>
        <li><a name="an1525"></a>
<code>bool list::empty()</code>:<blockquote>this member returns <code>true</code>
if the list contains no elements.</blockquote>
        <li><a name="an1526"></a>
<code>list::iterator list::end()</code>:<blockquote>this member
returns an iterator pointing beyond the last element in the list.</blockquote>
        <li><a name="an1527"></a>
<code>list::iterator list::erase()</code>:<blockquote>this member can be
used to erase a specific range of elements in the list:</blockquote>
            <ul>
            <li><code>erase(pos)</code> erases the element pointed to by <code>pos</code>. The
iterator <code>++pos</code> is returned.
            <li><code>erase(first, beyond)</code> erases elements indicated by the iterator
range <code>[first, beyond)</code>. <code>Beyond</code> is returned.
            </ul>
        <li><a name="an1528"></a>
<code>Type &amp;list::front()</code>:<blockquote>this member returns a
reference to the first element in the list. It is the responsibility of the
programmer to use this member only if the list is not empty.</blockquote>
        <li><a name="an1529"></a>
<code>... list::insert()</code>:<blockquote>this member can be used to
insert elements into the list. The return value depends on the version of
<code>insert()</code> that is called:</blockquote>
            <ul>
            <li><code>list::iterator insert(pos)</code> inserts a default value of type
<code>Type</code> at <code>pos</code>, <code>pos</code> is returned.
            <li><code>list::iterator insert(pos, value)</code> inserts <code>value</code> at
<code>pos</code>, <code>pos</code> is returned.
            <li><code>void insert(pos, first, beyond)</code> inserts the elements in the
                <a name="an1530"></a>
iterator range <a name="an1531"></a>
<code>[first, beyond)</code>.
            <li><code>void insert(pos, n, value)</code> inserts <code>n</code> elements having value
<code>value</code> at position <code>pos</code>.
            </ul>
        <li><a name="an1532"></a>
<code>void list&lt;Type&gt;::merge(list&lt;Type&gt; other)</code>:<blockquote>this
member function assumes that the current and other lists are sorted (see
below, the member <code>sort()</code>), and will, based on that assumption, insert the
elements of <code>other</code> into the current list in such a way that the modified
list remains sorted.  If both list are not sorted, the resulting list will be
ordered `as much as possible', given the initial ordering of the elements in
the two lists. <code>list&lt;Type&gt;::merge()</code> uses <code>Type::operator&lt;()</code> to sort the
data in the list, which operator must therefore be available.  The next
example illustrates the use of the <code>merge()</code> member: the list `<code>object</code>'
is not sorted, so the resulting list is ordered 'as much as possible'.
            <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;list&gt;
    using namespace std;

    void showlist(list&lt;string&gt; &amp;target)
    {
        for
        (
            list&lt;string&gt;::iterator from = target.begin();
            from != target.end();
            ++from
        )
            cout &lt;&lt; *from &lt;&lt; " ";

        cout &lt;&lt; endl;
    }

    int main()
    {
        list&lt;string&gt; first;
        list&lt;string&gt; second;

        first.push_back(string("alpha"));
        first.push_back(string("bravo"));
        first.push_back(string("golf"));
        first.push_back(string("quebec"));

        second.push_back(string("oscar"));
        second.push_back(string("mike"));
        second.push_back(string("november"));
        second.push_back(string("zulu"));

        first.merge(second);
        showlist(first);
    }
</pre>
    A subtlety is that <code>merge()</code> doesn't alter the list if the list itself
is used as argument: <code>object.merge(object)</code> won't change the list
`<code>object</code>'.</blockquote>
        <li><a name="an1533"></a>
<code>void list::pop_back()</code>:<blockquote>this member removes
the last element from the list. With an <a name="an1534"></a>
empty list nothing happens.</blockquote>
        <li><a name="an1535"></a>
<code>void list::pop_front()</code>:<blockquote>this member removes
the first element from the list. With an <a name="an1536"></a>
empty list nothing happens.</blockquote>
        <li><a name="an1537"></a>
<code>void list::push_back(value)</code>:<blockquote>this member
adds <code>value</code> to the end of the list.</blockquote>
        <li><a name="an1538"></a>
<code>void list::push_front(value)</code>:<blockquote>this member
adds <code>value</code> before the first element of the list.</blockquote>
        <li><a name="an1539"></a>
<code>void list::resize()</code>:<blockquote>this member can be used to
alter the number of elements that are currently stored in the list:</blockquote>
            <ul>
            <li><code>resize(n, value)</code> may be used to resize the list to a size of
<code>n</code>. <code>Value</code> is optional. If the list is expanded and <code>value</code> is not
provided, the extra elements are initialized to the <a name="an1540"></a>
default value of the
used data type, otherwise <code>value</code> is used to initialize extra elements.
            </ul>
        <li><a name="an1541"></a>
<code>list::reverse_iterator list::rbegin()</code>:<blockquote>
    <a name="an1542"></a>
 this member returns an iterator pointing to the last
element in the list.</blockquote>
        <li><a name="an1543"></a>
<code>void list::remove(value)</code>:<blockquote>this member removes
all occurrences of <code>value</code> from the list. In the following example, the two
strings `<code>Hello</code>' are removed from the list <code>object</code>:
            <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;list&gt;
    using namespace std;

    int main()
    {
        list&lt;string&gt; object;

        object.push_back(string("Hello"));
        object.push_back(string("World"));
        object.push_back(string("Hello"));
        object.push_back(string("World"));

        object.remove(string("Hello"));

        while (object.size())
        {
            cout &lt;&lt; object.front() &lt;&lt; endl;
            object.pop_front();
        }
    }
    /*
            Generated output:
        World
        World
    */
</pre>
</blockquote>
        <li><a name="an1544"></a>
<code>list::reverse_iterator list::rend()</code>:<blockquote>this
member returns an iterator pointing before the first element in the list.</blockquote>
        <li><a name="an1545"></a>
<code>size_t list::size()</code>:<blockquote>this member returns the
number of elements in the list.</blockquote>
        <li><a name="an1546"></a>
<code>void list::reverse()</code>:<blockquote>this member reverses the
order of the elements in the list. The element <code>back()</code> will become
<code>front()</code> and <em>vice versa</em>.</blockquote>
        <li><a name="an1547"></a>
<code>void list::sort()</code>:<blockquote>this member will sort the
list. Once the list has been sorted, An example of its use is given at the
description of the <code>unique()</code> member function below. <code>list&lt;Type&gt;::sort()</code>
uses <code>Type::operator&lt;()</code> to sort the data in the list, which operator must
therefore be available.</blockquote>
        <li><a name="an1548"></a>
<code>void list::splice(pos, object)</code>:<blockquote>this member
function transfers the contents of <code>object</code> to the current list, starting
the insertion at the iterator position <code>pos</code> of the object using the
<code>splice()</code> member. Following <code>splice()</code>, <code>object</code> is empty. For example:
         <pre>
#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;list&gt;
using namespace std;

int main()
{
    list&lt;string&gt; object;

    object.push_front(string("Hello"));
    object.push_back(string("World"));

    list&lt;string&gt; argument(object);

    object.splice(++object.begin(), argument);

    cout &lt;&lt; "Object contains " &lt;&lt; object.size() &lt;&lt; " elements, " &lt;&lt;
            "Argument contains " &lt;&lt; argument.size() &lt;&lt;
            " elements," &lt;&lt; endl;

    while (object.size())
    {
        cout &lt;&lt; object.front() &lt;&lt; endl;
        object.pop_front();
    }
}
</pre>
    Alternatively, <code>argument</code> may be followed by a iterator of <code>argument</code>,
indicating the first element of <code>argument</code> that should be spliced, or by two
iterators <code>begin</code> and <code>end</code> defining the iterator-range <code>[begin,
end)</code> on <code>argument</code> that should be spliced into <code>object</code>.</blockquote>
        <li><a name="an1549"></a>
<code>void list::swap()</code>:<blockquote>this member can be used to
swap two lists using identical data types.</blockquote>
        <li><a name="an1550"></a>
<code>void list::unique()</code>:<blockquote>operating on a sorted list,
this member function will remove all consecutively identical elements from the
list. <code>list&lt;Type&gt;::unique()</code> uses <code>Type::operator==()</code> to identify
identical data elements, which operator must therefore be available.  Here's
an example removing all multiply occurring words from the list:
            <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;list&gt;
    using namespace std;
                            // see the merge() example
    void showlist(list&lt;string&gt; &amp;target);
    void showlist(list&lt;string&gt; &amp;target)
    {
        for
        (
            list&lt;string&gt;::iterator from = target.begin();
            from != target.end();
            ++from
        )
            cout &lt;&lt; *from &lt;&lt; " ";

        cout &lt;&lt; endl;
    }


    int main()
    {
        string
            array[] =
            {
                "charley",
                "alpha",
                "bravo",
                "alpha"
            };

        list&lt;string&gt;
            target
            (
                array, array + sizeof(array)
                / sizeof(string)
            );

        cout &lt;&lt; "Initially we have: " &lt;&lt; endl;
        showlist(target);

        target.sort();
        cout &lt;&lt; "After sort() we have: " &lt;&lt; endl;
        showlist(target);

        target.unique();
        cout &lt;&lt; "After unique() we have: " &lt;&lt; endl;
        showlist(target);
    }
    /*
        Generated output:

        Initially we have:
        charley alpha bravo alpha
        After sort() we have:
        alpha alpha bravo charley
        After unique() we have:
        alpha bravo charley
    */
</pre>
</blockquote>
        </ul>
    </ul>
<p>
<a name="QUEUE"></a><a name="l178"></a>
<h3>12.3.3: The `queue' container</h3>
    <a name="containers/queue"></a>The <a name="an1551"></a>
<code>queue</code> class implements a <a name="an1552"></a>
queue data structure.  Before <code>queue</code>
containers can be used the following preprocessor directive must have been
specified: <a name="an1553"></a>

        <pre>
    #include &lt;queue&gt;
</pre>
    A queue is depicted in figure <a href="cplusplus12.html#queueFig">10</a>.
        <a name="queueFig"></a><p><center><img src="containers/queue.gif" align="bottom" alt="Figure 10 is shown here."/><br>
Figure 10: A queue data-structure
</center><p><br>

    In figure <a href="cplusplus12.html#queueFig">10</a> it is shown that a queue has one point (the
<em>back</em>) where items can be added to the queue, and one point (the <em>front</em>)
where items can be removed (read) from the queue. A <code>queue</code> is therefore
also called a <a name="an1554"></a>
<em>FIFO</em> data structure, for <a name="an1555"></a>
<em>first in, first out</em>. It is
most often used in situations where events should be handled in the same order
as they are generated.
<p>
The following constructors, operators, and member functions are available
for the <code>queue</code> container:
    <ul>
    <li> <a name="an1556"></a>
 Constructors:
        <ul>
        <li> A <code>queue</code> may be constructed empty:
        <pre>
    queue&lt;string&gt; object;
</pre>
        As with the <code>vector</code>, it is an error to refer to an element of an
empty queue.
        <li> A queue may be initialized using a <a name="an1557"></a>
copy constructor:
        <pre>
    extern queue&lt;string&gt; container;
    queue&lt;string&gt; object(container);
</pre>
    </ul>
    <li> The <code>queue</code> container only supports the basic operators for
containers.
    <li> The following <a name="an1558"></a>
member functions are available for queues:
        <ul>
        <li><a name="an1559"></a>
<code>Type &amp;queue::back()</code>:<blockquote>this member returns a
reference to the last element in the queue. It is the
    <a name="an1560"></a>
responsibility of the programmer to use the member only if the queue is
not empty.</blockquote>
        <li><a name="an1561"></a>
<code>bool queue::empty()</code>:<blockquote>this member returns
<code>true</code> if the queue contains no elements.</blockquote>
        <li><a name="an1562"></a>
<code>Type &amp;queue::front()</code>:<blockquote>this member returns a
reference to the first element in the queue. It is the responsibility of the
programmer to use the member only if the queue is not empty.</blockquote>
        
        <li><a name="an1563"></a>
<code>void queue::push(value)</code>:<blockquote>this member
adds <code>value</code> to the back of the queue.</blockquote>
        <li><a name="an1564"></a>
<code>void queue::pop()</code>:<blockquote>this member removes the element
at the front of the queue. Note that the element is <em>not</em> returned by this
member. Nothing happens if the member is called for an empty queue.  One might
wonder why <code>pop()</code> returns <code>void</code>, instead of a value of type <code>Type</code>
(cf. <code>front()</code>). Because of this, we must use <code>front()</code> first, and
thereafter <code>pop()</code> to examine and remove the queue's front element. However,
there is a good reason for this design. If <code>pop()</code> would return the
container's front element, it would have to return that element by <em>value</em>
rather than by <em>reference</em>, as a return by reference would create a dangling
pointer, since <code>pop()</code> would also remove that front element.  Return by
<em>value</em>, however, is inefficient in this case: it involves at least one copy
constructor call.  Since it is impossible for <code>pop()</code> to return a value
correctly and efficiently, it is more sensible to have <code>pop()</code> return no
value at all and to require clients to use <code>front()</code> to inspect the value at
the queue's front.</blockquote>
        <li><a name="an1565"></a>
<code>size_t queue::size()</code>:<blockquote>this member returns the
number of elements in the queue.</blockquote>
        </ul>
    </ul>
    Note that the queue does not support iterators or a subscript
operator. The only elements that can be accessed are its front and back
element.  A queue can be emptied by:
    <ul>
    <li> repeatedly removing its front element;
    <li> assigning an empty queue using the same data type to it;
    <li> having its destructor called.
    </ul>
<p>
<a name="l179"></a>
<h3>12.3.4: The `priority_queue' container</h3>
    <a name="containers/priority"></a>The <a name="an1566"></a>
<code>priority_queue</code> class implements a <a name="an1567"></a>
priority queue data structure.
Before <code>priority_queue</code> containers can be used the following preprocessor
directive must have been specified: <a name="an1568"></a>

        <pre>
    #include &lt;queue&gt;
</pre>
    A priority queue is identical to a <code>queue</code>, but allows the entry of data
elements according to <a name="an1569"></a>
priority rules. An example of a situation where the
priority queue is encountered in real-life is found at the check-in terminals
at airports. At a terminal the passengers normally stand in line to wait for
their turn to check in, but late passengers are usually allowed to jump the
queue: they receive a higher priority than other passengers.
<p>
The priority queue uses <code>operator&lt;()</code> of the data type stored in the
priority ueue to decide about the priority of the data elements. The
<em>smaller</em> the value, the <em>lower</em> the priority. So, the priority queue
<em>could</em> be used to sort values while they arrive.  A simple example of such
a priority queue application is the following program: it reads words from
<code>cin</code> and writes a sorted list of words to <code>cout</code>:
        <pre>
#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;queue&gt;
using namespace std;

int main()
{
    priority_queue&lt;string&gt; q;
    string word;

    while (cin &gt;&gt; word)
        q.push(word);

    while (q.size())
    {
        cout &lt;&lt; q.top() &lt;&lt; endl;
        q.pop();
    }
}
</pre>
    Unfortunately, the words are listed in reversed order: because of the
underlying <code>&lt;</code>-operator the words appearing later in the <a name="an1570"></a>
ASCII-sequence
appear first in the priority queue. A solution to that problem is to define a
<a name="an1571"></a>
wrapper class around the <code>string</code> datatype, in which the <code>operator&lt;()</code>
has been defined according to our wish, i.e., making sure that the words
appearing early in the ASCII-sequence will appear first in the queue. Here is
the modified program:
        <pre>
#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;queue&gt;

class Text
{
    std::string d_s;

    public:
        Text(std::string const &amp;str)
        :
            d_s(str)
        {}
        operator std::string const &amp;() const
        {
            return d_s;
        }
        bool operator&lt;(Text const &amp;right) const
        {
            return d_s &gt; right.d_s;
        }
};

using namespace std;

int main()
{
    priority_queue&lt;Text&gt; q;
    string word;

    while (cin &gt;&gt; word)
        q.push(word);

    while (q.size())
    {
        word = q.top();
        cout &lt;&lt; word &lt;&lt; endl;
        q.pop();
    }
}
</pre>
    In the above program the wrapper class defines the <code>operator&lt;()</code> just the
other way around than the <code>string</code> class itself, resulting in the preferred
ordering. Other possibilities would be to store the contents of the priority
queue in, e.g., a vector, from which the elements can be read in reversed
order.
<p>
The following constructors, operators, and member functions are available
for the <code>priority_queue</code> container:
    <ul>
    <li> <a name="an1572"></a>
 Constructors:
        <ul>
        <li> A <code>priority_queue</code> may be constructed empty:
        <pre>
    priority_queue&lt;string&gt; object;
</pre>
        As with the <code>vector</code>, it is an error to refer to an element of an
empty priority queue.
        <li> A priority queue may be initialized using a <a name="an1573"></a>
copy constructor:
        <pre>
    extern priority_queue&lt;string&gt; container;
    priority_queue&lt;string&gt; object(container);
</pre>
    </ul>
    <li> The <code>priority_queue</code> only supports the basic operators of
containers.
    <li> The following <a name="an1574"></a>
member functions are available for priority queues:
        <ul>
        <li><a name="an1575"></a>
<code>bool priority_queue::empty()</code>:<blockquote>this
member returns <code>true</code> if the priority queue contains no elements.</blockquote>
        <li><a name="an1576"></a>
<code>void priority_queue::push(value)</code>:<blockquote>this
member inserts <code>value</code> at the appropriate position in the priority queue.</blockquote>
        <li><a name="an1577"></a>
<code>void priority_queue::pop()</code>:<blockquote>this member
removes the element at the top of the priority queue. Note that the element
is <em>not</em> returned by this member. Nothing happens if this member is called
for and empty priority queue. See section <a href="cplusplus12.html#QUEUE">12.3.3</a> for a discussion about
the reason why <code>pop()</code> has return type <code>void</code>.</blockquote>
        <li><a name="an1578"></a>
<code>size_t priority_queue::size()</code>:<blockquote>this
member returns the number of elements in the priority queue.</blockquote>
        <li><a name="an1579"></a>
<code>Type &amp;priority_queue::top()</code>:<blockquote>this member
returns a reference to the first element of the priority queue. It is the
    <a name="an1580"></a>
responsibility of the programmer to use the member only if the
priority queue is not empty.</blockquote>
        </ul>
    </ul>
    Note that the priority queue does not support iterators or a subscript
operator. The only element that can be accessed is its top element.  A
priority queue can be emptied by:
    <ul>
    <li> repeatedly removing its top element;
    <li> assigning an empty queue using the same data type to it;
    <li> having its destructor called.
    </ul>
<p>
<a name="l180"></a>
<h3>12.3.5: The `deque' container</h3>
    <a name="containers/deque"></a>The <a name="an1581"></a>
<code>deque</code> (pronounce: `deck') class implements a
    <a name="an1582"></a>
doubly ended queue data structure (deque).  Before <code>deque</code> containers
can be used the following preprocessor directive must have been specified:
<a name="an1583"></a>

        <pre>
    #include &lt;deque&gt;
</pre>
    A <em>deque</em> is comparable to a queue, but it allows reading and writing at
both ends. Actually, the <code>deque</code> data type supports a lot more
functionality than the <code>queue</code>, as will be clear from the following overview
of available member functions. A <code>deque</code> is a
combination of a <code>vector</code> and two queues, operating at both ends of the
vector. In situations where random insertions and the addition and/or removal
of elements at one or both sides of the vector occurs frequently, using
a <code>deque</code> should be considered.
<p>
The following constructors, operators, and member functions are available for
deques:
    <ul>
    <li> <a name="an1584"></a>
 Constructors:
        <ul>
        <li> A <code>deque</code> may be constructed empty:
        <pre>
    deque&lt;string&gt;
        object;
</pre>
        As with the <code>vector</code>, it is an error to refer to an element of an
empty deque.
        <li> A deque may be initialized to  a certain number of
elements. By default, if the initialization value is not explicitly mentioned,
the default value or default constructor for the actual data type is used. For
example:
        <pre>
    deque&lt;string&gt; object(5, string("Hello")), // initialize to 5 Hello's
    deque&lt;string&gt; container(10);              // and to 10 empty strings
</pre>
        <li> A deque may be initialized using a two iterators. To
initialize a deque with elements 5 until 10 (including the last one) of a
<code>vector&lt;string&gt;</code> the following construction may be used:
        <pre>
    extern vector&lt;string&gt; container;
    deque&lt;string&gt; object(&amp;container[5], &amp;container[11]);
</pre>
        <li> A deque may be initialized using a <a name="an1585"></a>
copy constructor:
        <pre>
    extern deque&lt;string&gt; container;
    deque&lt;string&gt; object(container);
</pre>
    </ul>
    <li> Apart from the standard operators for containers, the deque
supports the <a name="an1586"></a>
index operator, which may be used to retrieve or reassign
<a name="an1587"></a>
random elements of the deque. Note that the elements which are indexed
must exist.
    <li> The following <a name="an1588"></a>
member functions are available for deques:
        <ul>
        <li><a name="an1589"></a>
<code>Type &amp;deque::back()</code>:<blockquote>this member returns a
reference to the last element in the deque. It is the
    <a name="an1590"></a>
responsibility of the programmer to use the member only if the deque is
not empty.</blockquote>
        <li><a name="an1591"></a>
<code>deque::iterator deque::begin()</code>:<blockquote>this member
returns an <a name="an1592"></a>
iterator pointing to the first element in the deque. </blockquote>
        <li><a name="an1593"></a>
<code>void deque::clear()</code>:<blockquote>this member erases all
elements in the deque.</blockquote>
        <li><a name="an1594"></a>
<code>bool deque::empty()</code>:<blockquote>this member returns
<code>true</code> if the deque contains no elements.</blockquote>
        <li><a name="an1595"></a>
<code>deque::iterator deque::end()</code>:<blockquote>this member
returns an iterator pointing beyond the last element in the deque. </blockquote>
        <li><a name="an1596"></a>
<code>deque::iterator deque::erase()</code>:<blockquote>the member can
be used to erase a specific range of elements in the deque:</blockquote>
            <ul>
            <li><code>erase(pos)</code> erases the element pointed to by <code>pos</code>. The
iterator <code>++pos</code> is returned.
            <li><code>erase(first, beyond)</code> erases elements indicated by the iterator
range <code>[first, beyond)</code>. <code>Beyond</code> is returned.
            </ul>
        <li><a name="an1597"></a>
<code>Type &amp;deque::front()</code>:<blockquote>this member returns a
reference to the first element in the deque. It is the responsibility of the
programmer to use the member only if the deque is not empty.</blockquote>
        <li><a name="an1598"></a>
<code>... deque::insert()</code>:<blockquote>this member can be used to
insert elements starting at a certain position. The return value depends on
the version of <code>insert()</code> that is called:</blockquote>
            <ul>
            <li><code>deque::iterator insert(pos)</code> inserts a default value of type
<code>Type</code> at <code>pos</code>, <code>pos</code> is returned.
            <li><code>deque::iterator insert(pos, value)</code> inserts <code>value</code> at
<code>pos</code>, <code>pos</code> is returned.
            <li><code>void insert(pos, first, beyond)</code> inserts the elements in the
                <a name="an1599"></a>
iterator range <a name="an1600"></a>
<code>[first, beyond)</code>.
            <li><code>void insert(pos, n, value)</code> inserts <code>n</code> elements having value
<code>value</code> starting at iterator position <code>pos</code>.
            </ul>
        <li><a name="an1601"></a>
<code>void deque::pop_back()</code>:<blockquote>this member removes
the last element from the deque. With an <a name="an1602"></a>
empty deque nothing happens.</blockquote>
        <li><a name="an1603"></a>
<code>void deque::pop_front()</code>:<blockquote>this member removes
the first element from the deque. With an <a name="an1604"></a>
empty deque nothing happens.</blockquote>
        <li><a name="an1605"></a>
<code>void deque::push_back(value)</code>:<blockquote>this member
adds <code>value</code> to the end of the deque.</blockquote>
        <li><a name="an1606"></a>
<code>void deque::push_front(value)</code>:<blockquote>this member
adds <code>value</code> before the first element of the deque.</blockquote>
        <li><a name="an1607"></a>
<code>void deque::resize()</code>:<blockquote>this member can be used
to alter the number of elements that are currently stored in the deque:</blockquote>
            <ul>
            <li><code>resize(n, value)</code> may be used to resize the deque to a size of
<code>n</code>. <code>Value</code> is optional. If the deque is expanded and <code>value</code> is not
provided, the additional elements are initialized to the <a name="an1608"></a>
default value of
the used data type, otherwise <code>value</code> is used
to initialize extra elements.
            </ul>
        <li><a name="an1609"></a>
<code>deque::reverse_iterator deque::rbegin()</code>:<blockquote>
    <a name="an1610"></a>
 this member returns an iterator pointing to the last
element in the deque.</blockquote>
        <li><a name="an1611"></a>
<code>deque::reverse_iterator deque::rend()</code>:<blockquote>this
member returns an iterator pointing before the first element in the deque.</blockquote>
        <li><a name="an1612"></a>
<code>size_t deque::size()</code>:<blockquote>this member returns the
number of elements in the deque.</blockquote>
        <li><a name="an1613"></a>
<code>void deque::swap(argument)</code>:<blockquote>this member can be
used to swap two deques using identical data types.</blockquote>
        </ul>
    </ul>
<p>
<a name="MAP"></a><a name="l181"></a>
<h3>12.3.6: The `map' container</h3>
    <a name="containers/map"></a>The <a name="an1614"></a>
<code>map</code> class implements a (sorted) <a name="an1615"></a>
associative array. Before <code>map</code>
containers can be used, the following preprocessor directive must have been
specified: <a name="an1616"></a>

        <pre>
    #include &lt;map&gt;
</pre>
    A <code>map</code> is filled with <a name="an1617"></a>
<em>key/value</em> pairs, which may be of any
container-acceptable type. Since types are associated with both the key and
the value, we must specify <a name="an1618"></a>
two types in the <a name="an1619"></a>
angle bracket notation,
comparable to the specification we've seen with the <code>pair</code> (section
<a href="cplusplus12.html#PAIR">12.2</a>) container. The first type represents the type of the key, the
second type represents the type of the value. For example, a <code>map</code> in which
the key is a <code>string</code> and the value is a <code>double</code> can be defined as
follows:
        <pre>
    map&lt;string, double&gt; object;
</pre>
    The <a name="an1620"></a>
<em>key</em> is used to access its associated information. That
information is called the <a name="an1621"></a>
<em>value</em>. For example, a <a name="an1622"></a>
phone book uses the
<a name="an1623"></a>
names of people as the key, and uses the telephone number and maybe other
information (e.g., the zip-code, the address, the profession) as the
value. Since a <code>map</code> sorts its keys, the <code>key</code>'s <code>operator&lt;()</code> must be
defined, and it must be sensible to use it. For example, it is generally a bad
idea to use pointers for keys, as sorting pointers is something different than
sorting the values these pointers point to.
<p>
The two fundamental operations on maps are the <a name="an1624"></a>
storage of <em>Key/Value</em>
combinations, and the <a name="an1625"></a>
retrieval of values, given their keys. The index
operator, using a key as the index, can be used for both. If the index
operator is used as <em>lvalue</em>, insertion will be performed. If it is used as
<em>rvalue</em>, the key's associated value is retrieved.  Each key can be stored
only once in a <code>map</code>. If the same key is entered again, the new value
replaces the formerly stored value, which is lost.
<p>
A specific key/value combination can be implicitly or explicitly inserted into
a <code>map</code>. If <a name="an1626"></a>
explicit insertion is required, the key/value combination
must be constructed first. For this, every <code>map</code> defines a <a name="an1627"></a>
<code>value_type</code>
which may be used to <a name="an1628"></a>
create values that can be stored in the <code>map</code>. For
example, a value for a <code>map&lt;string, int&gt;</code> can be constructed as follows:
        <pre>
    map&lt;string, int&gt;::value_type siValue("Hello", 1);
</pre>
    The <code>value_type</code> is associated with the <code>map&lt;string, int&gt;</code>: the
type of the key is <code>string</code>, the type of the value is <code>int</code>. Anonymous
<code>value_type</code> objects are also often used. E.g.,
        <pre>
    map&lt;string, int&gt;::value_type("Hello", 1);
</pre>
    Instead of using the line <code>map&lt;string, int&gt;::value_type(...)</code> over
and over again, a <a name="an1629"></a>
<code>typedef</code> is often used to <a name="an1630"></a>
reduce typing and to improve
<a name="an1631"></a>
legibility:
        <pre>
    typedef map&lt;string, int&gt;::value_type StringIntValue
</pre>
    Using this typedef, values for the <code>map&lt;string, int&gt;</code> may now be
constructed using:
        <pre>
    StringIntValue("Hello", 1);
</pre>
    Finally, <code>pairs</code> may be used to represent key/value combinations used by
maps:
        <pre>
    pair&lt;string, int&gt;("Hello", 1);
</pre>
<p>
The following constructors, operators, and member functions are available
for the <code>map</code> container:
    
    <ul>
    <li> <a name="an1632"></a>
 Constructors:
        
        <ul>
        <li> A <code>map</code> may be constructed empty:
        <pre>
    map&lt;string, int&gt; object;
</pre>
    Note that the values stored in maps may be containers themselves. For
example, the following defines a <code>map</code> in which the value is a <code>pair</code>: a
container <a name="an1633"></a>
 <a name="an1634"></a>
 nested in another
container:
        <pre>
    map&lt;string, pair&lt;string, string&gt; &gt; object;
</pre>
    Note the blank space between the two closing angle brackets <code>&gt;</code>: this
is obligatory, as the immediate
    <a name="an1635"></a>
 concatenation of the two
angle closing brackets would be interpreted by the compiler as a
    right shift operator (<code>operator</code>>><code>()</code>), which is not what
we want here.
        <li> A map may be initialized using two iterators.  The iterators may
either point to <code>value_type</code> values for the map to be constructed, or to
plain <a name="an1636"></a>
<code>pair</code> objects (see section <a href="cplusplus12.html#PAIR">12.2</a>). If pairs are used, their
<a name="an1637"></a>
<code>first</code> elements represent the keys, and their <code>second</code> elements represent
the values to be used. For example:
        <pre>
    pair&lt;string, int&gt; pa[] =
    {
        pair&lt;string,int&gt;("one", 1),
        pair&lt;string,int&gt;("two", 2),
        pair&lt;string,int&gt;("three", 3),
    };

    map&lt;string, int&gt; object(&amp;pa[0], &amp;pa[3]);
</pre>
    In this example, <code>map&lt;string, int&gt;::value_type</code> could have been written
instead of <code>pair&lt;string, int&gt;</code> as well.
<p>
When <code>begin</code> is the first iterator used to construct a map and
<code>end</code> the second iterator, <code>[begin, end)</code> will be used to initialize
the map. Maybe <a name="an1638"></a>
contrary to intuition, the <code>map</code> constructor
will only enter <em>new</em> keys.  If the last element of <code>pa</code> would have been
<code>"one", 3</code>, only <em>two</em> elements would have entered the <code>map</code>: <code>"one",
1</code> and <code>"two", 2</code>. The value <code>"one", 3</code> would have been
    <a name="an1639"></a>
silently ignored.
<p>
The <code>map</code> receives its own copies of the data to which the iterators
point. This is illustrated by the following example:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;map&gt;
    using namespace std;

    class MyClass
    {
        public:
            MyClass()
            {
                cout &lt;&lt; "MyClass constructor\n";
            }
            MyClass(const MyClass &amp;other)
            {
                cout &lt;&lt; "MyClass copy constructor\n";
            }
            ~MyClass()
            {
                cout &lt;&lt; "MyClass destructor\n";
            }
    };

    int main()
    {
        pair&lt;string, MyClass&gt; pairs[] =
        {
            pair&lt;string, MyClass&gt;("one", MyClass()),
        };
        cout &lt;&lt; "pairs constructed\n";

        map&lt;string, MyClass&gt; mapsm(&amp;pairs[0], &amp;pairs[1]);
        cout &lt;&lt; "mapsm constructed\n";
    }
    /*
        Generated output:
    MyClass constructor
    MyClass copy constructor
    MyClass destructor
    pairs constructed
    MyClass copy constructor
    MyClass copy constructor
    MyClass destructor
    mapsm constructed
    MyClass destructor
    */
</pre>
    When tracing the output of this program, we see that, first, the
constructor of a <code>MyClass</code> object is called to initialize the anonymous
element of the array <code>pairs</code>. This object is then copied into the first
element of the array <code>pairs</code> by the copy constructor. Next, the original
element is not needed anymore, and is destroyed. At that point the array
<code>pairs</code> has been constructed. Thereupon, the <code>map</code> constructs a temporary
<code>pair</code> object, which is used to construct the map element. Having
constructed the map element, the temporary <code>pair</code> objects is
destroyed. Eventually, when the program terminates, the <code>pair</code> element
stored in the <code>map</code> is destroyed too.
        <li> A map may be initialized using a <a name="an1640"></a>
copy constructor:
        <pre>
    extern map&lt;string, int&gt; container;
    map&lt;string, int&gt; object(container);
</pre>
        </ul>
        
    <li> Apart from the standard operators for containers, the <code>map</code>
supports the <a name="an1641"></a>
index operator, which may be used to retrieve or reassign
individual elements of the map. Here, the argument of the index operator is a
key.  If the provided key is not available in the <code>map</code>, a new data element
is automatically added to the <code>map</code>, using the default value or default
constructor to initialize the value part of the new element. This default
value is returned if the index operator is used as an <a name="an1642"></a>
rvalue.
<p>
When initializing a new or reassigning another element of the map, the type of
the right-hand side of the assignment operator must be equal to (or promotable
to) the type of the map's value part. E.g., to add or change the value of
element <code>"two"</code> in a map, the following statement can be used:
        <pre>
    mapsm["two"] = MyClass();
</pre>
    <li> The <code>map</code> class has the following <a name="an1643"></a>
 member
functions:
        
        <ul>
        <li><a name="an1644"></a>
<code>map::iterator map::begin()</code>:<blockquote>this member
returns an <a name="an1645"></a>
iterator pointing to the first element of the map. </blockquote>
        <li><a name="an1646"></a>
<code>map::clear()</code>:<blockquote>this member erases all elements from the map.</blockquote>
        <li><a name="an1647"></a>
<code>size_t map::count(key)</code>:<blockquote>this member returns 1 if
the provided key is available in the <code>map</code>, otherwise 0 is returned.</blockquote>
        <li><a name="an1648"></a>
<code>bool map::empty()</code>:<blockquote>this member returns <code>true</code> if
the map contains no elements.</blockquote>
        <li><a name="an1649"></a>
<code>map::iterator map::end()</code>:<blockquote>this member
returns an iterator pointing beyond the last element of the map.</blockquote>
        <li><a name="an1650"></a>
<code>pair&lt;map::iterator, map::iterator&gt; map::equal_range(key)</code>:<blockquote>this
member returns a pair of iterators, being respectively the return values of
the member functions <code>lower_bound()</code> and <code>upper_bound()</code>, introduced below.
An example illustrating these member functions is given at the
discussion of the member function <code>upper_bound()</code>.</blockquote>
        <li><a name="an1651"></a>
<code>... map::erase()</code>:<blockquote>this member can be
used to erase a specific element or range of elements from the map:</blockquote>
            <ul>
            <li><code>bool erase(key)</code> erases the element having the
given <code>key</code> from the <code>map</code>. <code>True</code> is returned if the value was removed,
<code>false</code> if the map did not contain an element using the given <code>key</code>.
            <li><code>void erase(pos)</code> erases the element pointed to by the iterator
<code>pos</code>.
            <li><code>void erase(first, beyond)</code> erases all elements indicated by
the iterator range <code>[first, beyond)</code>.
            </ul>
        <li><a name="an1652"></a>
<code>map::iterator map::find(key)</code>:<blockquote>this member returns
an iterator to the element having the given key. If the element isn't
available, <code>end()</code> is returned. The following example illustrates the use of
the <code>find()</code> member function:</blockquote>
    <pre>
    #include &lt;iostream&gt;
    #include &lt;map&gt;
    using namespace std;

    int main()
    {
        map&lt;string, int&gt; object;

        object["one"] = 1;

        map&lt;string, int&gt;::iterator it = object.find("one");

        cout &lt;&lt; "`one' " &lt;&lt;
                (it == object.end() ? "not " : "") &lt;&lt; "found\n";

        it = object.find("three");

        cout &lt;&lt; "`three' " &lt;&lt;
                (it == object.end() ? "not " : "") &lt;&lt; "found\n";
    }
    /*
        Generated output:
    `one' found
    `three' not found
    */
</pre>
        <li><a name="an1653"></a>
<code>... map::insert()</code>:<blockquote>this member can be used to
insert elements into the map. It will, however, not replace the values
associated with already existing keys by new values. Its return value depends
on the version of <code>insert()</code> that is called:</blockquote>
            <ul>
            <li><code>pair&lt;map::iterator, bool&gt; insert(keyvalue)</code> inserts
a new <code>map::value_type</code> into the map. The return value is a
<a name="an1654"></a>
<code>pair&lt;map::iterator, bool&gt;</code>.  If the returned <a name="an1655"></a>
<code>bool</code> field is <code>true</code>,
<code>keyvalue</code> was inserted into the map. The value <code>false</code> indicates that the
key that was specified in <code>keyvalue</code> was already available in the map, and
so <code>keyvalue</code> was not inserted into the map.  In both cases the
<code>map::iterator</code> field points to the data element having the
<code>key</code> that was specified in <code>keyvalue</code>. The use of this variant of
<code>insert()</code> is illustrated by the following example:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;string&gt;
    #include &lt;map&gt;
    using namespace std;

    int main()
    {
        pair&lt;string, int&gt; pa[] =
        {
            pair&lt;string,int&gt;("one", 10),
            pair&lt;string,int&gt;("two", 20),
            pair&lt;string,int&gt;("three", 30),
        };
        map&lt;string, int&gt; object(&amp;pa[0], &amp;pa[3]);

                // {four, 40} and `true' is returned
        pair&lt;map&lt;string, int&gt;::iterator, bool&gt;
            ret = object.insert
                    (
                        map&lt;string, int&gt;::value_type
                        ("four", 40)
                    );

        cout &lt;&lt; boolalpha;

        cout &lt;&lt; ret.first-&gt;first &lt;&lt; " " &lt;&lt;
            ret.first-&gt;second &lt;&lt; " " &lt;&lt;
            ret.second &lt;&lt; " " &lt;&lt; object["four"] &lt;&lt; endl;

                // {four, 40} and `false' is returned
        ret = object.insert
                    (
                        map&lt;string, int&gt;::value_type
                        ("four", 0)
                    );

        cout &lt;&lt; ret.first-&gt;first &lt;&lt; " " &lt;&lt;
            ret.first-&gt;second &lt;&lt; " " &lt;&lt;
            ret.second &lt;&lt; " " &lt;&lt; object["four"] &lt;&lt; endl;
    }
    /*
        Generated output:

        four 40 true 40
        four 40 false 40
    */
</pre>
    Note the somewhat peculiar constructions like
        <pre>
    cout &lt;&lt; ret.first-&gt;first &lt;&lt; " " &lt;&lt; ret.first-&gt;second &lt;&lt; ...
</pre>
    Realize that `<code>ret</code>' is equal to the <code>pair</code> returned by the
<code>insert()</code> member function. Its `<code>first</code>' field is an iterator into the
<code>map&lt;string, int&gt;</code>, so it can be considered a pointer to a <code>map&lt;string,
int&gt;::value_type</code>. These value types themselves are pairs too, having
`<code>first</code>' and `<code>second</code>' fields. Consequently, `<code>ret.first-&gt;first</code>' is
the <em>key</em> of the map value (a <code>string</code>), and `<code>ret.first-&gt;second</code>' is
the <em>value</em> (an <code>int</code>).
            <li><code>map::iterator insert(pos, keyvalue)</code>. This way a
<code>map::value_type</code> may also be inserted into the map. <code>pos</code> is ignored, and
an iterator to the inserted element is returned.
            <li><code>void insert(first, beyond)</code> inserts the (<code>map::value_type</code>)
elements pointed to by the <a name="an1656"></a>
iterator range <a name="an1657"></a>
<code>[first, beyond)</code>.
            </ul>
        <li><a name="an1658"></a>
<code>map::iterator map::lower_bound(key)</code>:<blockquote>this member returns an iterator pointing to the first
<code>keyvalue</code> element of which the <code>key</code> is at least equal to the specified
<code>key</code>.  If no such element exists, the function returns
<code>map::end()</code>.</blockquote>
        <li><a name="an1659"></a>
<code>map::reverse_iterator map::rbegin()</code>:<blockquote>
    <a name="an1660"></a>
 this member returns an iterator pointing to the last
element of the map.</blockquote>
        <li><a name="an1661"></a>
<code>map::reverse_iterator map::rend()</code>:<blockquote>this member
returns an iterator pointing before the first element of the map.</blockquote>
        <li><a name="an1662"></a>
<code>size_t map::size()</code>:<blockquote>this member returns the
number of elements in the map.</blockquote>
        <li><a name="an1663"></a>
<code>void map::swap(argument)</code>:<blockquote>this member can be used
to swap two maps, using identical key/value types.</blockquote>
        <li><a name="an1664"></a>
<code>map::iterator map::upper_bound(key)</code>:<blockquote>this member returns an iterator pointing to the first
<code>keyvalue</code> element having a <code>key</code> exceeding the specified <code>key</code>.  If no
such element exists, the function returns <code>map::end()</code>.  The following
example illustrates the member functions <code>equal_range()</code>, <code>lower_bound()</code>
and <code>upper_bound()</code>:
            <pre>
    #include &lt;iostream&gt;
    #include &lt;map&gt;
    using namespace std;

    int main()
    {
        pair&lt;string, int&gt; pa[] =
        {
            pair&lt;string,int&gt;("one", 10),
            pair&lt;string,int&gt;("two", 20),
            pair&lt;string,int&gt;("three", 30),
        };
        map&lt;string, int&gt; object(&amp;pa[0], &amp;pa[3]);
        map&lt;string, int&gt;::iterator it;

        if ((it = object.lower_bound("tw")) != object.end())
            cout &lt;&lt; "lower-bound `tw' is available, it is: " &lt;&lt;
                    it-&gt;first &lt;&lt; endl;

        if (object.lower_bound("twoo") == object.end())
            cout &lt;&lt; "lower-bound `twoo' not available" &lt;&lt; endl;

        cout &lt;&lt; "lower-bound two: " &lt;&lt;
                object.lower_bound("two")-&gt;first &lt;&lt;
                " is available\n";

        if ((it = object.upper_bound("tw")) != object.end())
            cout &lt;&lt; "upper-bound `tw' is available, it is: " &lt;&lt;
                    it-&gt;first &lt;&lt; endl;

        if (object.upper_bound("twoo") == object.end())
            cout &lt;&lt; "upper-bound `twoo' not available" &lt;&lt; endl;

        if (object.upper_bound("two") == object.end())
            cout &lt;&lt; "upper-bound `two' not available" &lt;&lt; endl;

        pair
        &lt;
            map&lt;string, int&gt;::iterator,
            map&lt;string, int&gt;::iterator
        &gt;
            p = object.equal_range("two");

        cout &lt;&lt; "equal range: `first' points to " &lt;&lt;
                    p.first-&gt;first &lt;&lt; ", `second' is " &lt;&lt;
            (
                p.second == object.end() ?
                    "not available"
                :
                    p.second-&gt;first
            ) &lt;&lt;
            endl;
    }
    /*
        Generated output:

            lower-bound `tw' is available, it is: two
            lower-bound `twoo' not available
            lower-bound two: two is available
            upper-bound `tw' is available, it is: two
            upper-bound `twoo' not available
            upper-bound `two' not available
            equal range: `first' points to two, `second' is not available
    */
</pre>
        </blockquote>
    </ul>
    
    </ul>
    
    As mentioned at the beginning of this section, the <code>map</code> represents a
sorted associative array. In a <code>map</code> the keys are sorted. If an application
must <a name="an1665"></a>
visit all elements in a map (or just the keys or the values)
the <code>begin()</code> and <code>end()</code> iterators must be used. The following example
shows how to make a simple table listing all keys and values in a map:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;iomanip&gt;
    #include &lt;map&gt;

    using namespace std;

    int main()
    {
        pair&lt;string, int&gt;
            pa[] =
            {
                pair&lt;string,int&gt;("one", 10),
                pair&lt;string,int&gt;("two", 20),
                pair&lt;string,int&gt;("three", 30),
            };
        map&lt;string, int&gt;
            object(&amp;pa[0], &amp;pa[3]);

        for
        (
            map&lt;string, int&gt;::iterator it = object.begin();
                it != object.end();
                    ++it
        )
            cout &lt;&lt; setw(5) &lt;&lt; it-&gt;first.c_str() &lt;&lt;
                    setw(5) &lt;&lt; it-&gt;second &lt;&lt; endl;
    }
    /*
        Generated output:
      one   10
    three   30
      two   20
    */
</pre>
<p>
<a name="MULTIMAP"></a><a name="l182"></a>
<h3>12.3.7: The `multimap' container</h3>
    <a name="containers/multimap"></a>Like the <code>map</code>, the <a name="an1666"></a>
<code>multimap</code> class implements a (sorted)
    <a name="an1667"></a>
associative array. Before <code>multimap</code> containers can be used the
following preprocessor directive must have been specified: <a name="an1668"></a>

        <pre>
    #include &lt;map&gt;
</pre>
    The main difference between the <code>map</code> and the <code>multimap</code> is that the
multimap supports multiple values associated with the same key, whereas the
map contains single-valued keys. Note that the multimap also accepts multiple
identical values associated with identical keys.
<p>
The <code>map</code> and the <code>multimap</code> <a name="an1669"></a>
 have the same
set of member functions, with the exception of the <a name="an1670"></a>
index operator
(<a name="an1671"></a>
<code>operator[]()</code>), which is not supported <a name="an1672"></a>
 with
the multimap. This is understandable: if multiple entries of the same key are
allowed, which of the possible values should be returned for <code>object[key]</code>?
<p>
Refer to section <a href="cplusplus12.html#MAP">12.3.6</a> for an <a name="an1673"></a>
 overview of
the <code>multimap</code> member functions. Some member functions, however, deserve
additional attention when used in the context of the <code>multimap</code>
container. These members are discussed below.
    <ul>
        <li><a name="an1674"></a>
<code>size_t map::count(key)</code>:<blockquote>this member returns the
number of entries in the multimap associated with the given <code>key</code>.</blockquote>
        <li><a name="an1675"></a>
<code>... multimap::erase()</code>:<blockquote>this member can be
used to erase elements from the map:</blockquote>
            <ul>
            <li><code>size_t erase(key)</code> erases all elements having the
given <code>key</code>. The number of erased elements is returned.
            <li><code>void erase(pos)</code> erases the single element pointed to by
<code>pos</code>. Other elements possibly having the same keys are not erased.
            <li><code>void erase(first, beyond)</code> erases all elements indicated by
the iterator range <code>[first, beyond)</code>.
            </ul>
        <li><a name="an1676"></a>
<code>pair&lt;multimap::iterator, multimap::iterator&gt; multimap::equal_range(key)</code>:<blockquote>this member function returns a pair of iterators, being respectively
the return values of <code>multimap::lower_bound()</code> and
<code>multimap::upper_bound()</code>, introduced below.  The function provides a simple
means to determine all elements in the <code>multimap</code> that have the same
<code>keys</code>. An example illustrating the use of these member functions is given
at the end of this section.</blockquote>
        <li><a name="an1677"></a>
<code>multimap::iterator multimap::find(key)</code>:<blockquote>this
member returns an iterator pointing to the first value whose key is
<code>key</code>. If the element isn't available, <code>multimap::end()</code> is returned. The
iterator could be incremented to visit all elements having the same <code>key</code>
until it is either <code>multimap::end()</code>, or the iterator's <code>first</code> member is
not equal to <code>key</code> anymore.</blockquote>
        <li><a name="an1678"></a>
<code>multimap::iterator multimap::insert()</code>:<blockquote>this
member function normally succeeds, and so a <a name="an1679"></a>
<em>multimap::iterator</em> is
returned, instead of a <code>pair&lt;multimap::iterator, bool&gt;</code> as returned with the
<code>map</code> container. The returned iterator points to the newly added element.</blockquote>
    </ul>
    Although the functions <code>lower_bound()</code> and <code>upper_bound()</code> act
identically in the <code>map</code> and <code>multimap</code> containers, their operation in a
<code>multimap</code> deserves some additional attention. The next example illustrates
<code>multimap::lower_bound()</code>, <code>multimap::upper_bound()</code> and
<code>multimap::equal_range</code> applied to a <code>multimap</code>:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;map&gt;
    using namespace std;

    int main()
    {
        pair&lt;string, int&gt; pa[] =
        {
            pair&lt;string,int&gt;("alpha", 1),
            pair&lt;string,int&gt;("bravo", 2),
            pair&lt;string,int&gt;("charley", 3),
            pair&lt;string,int&gt;("bravo", 6),   // unordered `bravo' values
            pair&lt;string,int&gt;("delta", 5),
            pair&lt;string,int&gt;("bravo", 4),
        };
        multimap&lt;string, int&gt; object(&amp;pa[0], &amp;pa[6]);

        typedef multimap&lt;string, int&gt;::iterator msiIterator;

        msiIterator it = object.lower_bound("brava");

        cout &lt;&lt; "Lower bound for `brava': " &lt;&lt;
                it-&gt;first &lt;&lt; ", " &lt;&lt; it-&gt;second &lt;&lt; endl;

        it = object.upper_bound("bravu");

        cout &lt;&lt; "Upper bound for `bravu': " &lt;&lt;
                it-&gt;first &lt;&lt; ", " &lt;&lt; it-&gt;second &lt;&lt; endl;

        pair&lt;msiIterator, msiIterator&gt;
            itPair = object.equal_range("bravo");

        cout &lt;&lt; "Equal range for `bravo':\n";
        for (it = itPair.first; it != itPair.second; ++it)
            cout &lt;&lt; it-&gt;first &lt;&lt; ", " &lt;&lt; it-&gt;second &lt;&lt; endl;
        cout &lt;&lt; "Upper bound: " &lt;&lt; it-&gt;first &lt;&lt; ", " &lt;&lt; it-&gt;second &lt;&lt; endl;

        cout &lt;&lt; "Equal range for `brav':\n";
        itPair = object.equal_range("brav");
        for (it = itPair.first; it != itPair.second; ++it)
            cout &lt;&lt; it-&gt;first &lt;&lt; ", " &lt;&lt; it-&gt;second &lt;&lt; endl;
        cout &lt;&lt; "Upper bound: " &lt;&lt; it-&gt;first &lt;&lt; ", " &lt;&lt; it-&gt;second &lt;&lt; endl;
    }
    /*
        Generated output:

        Lower bound for `brava': bravo, 2
        Upper bound for `bravu': charley, 3
        Equal range for `bravo':
        bravo, 2
        bravo, 6
        bravo, 4
        Upper bound: charley, 3
        Equal range for `brav':
        Upper bound: bravo, 2
    */
</pre>
    In particular note the following characteristics:
    <ul>
    <li><code>lower_bound()</code> and <code>upper_bound()</code> produce the same result for
non-existing keys: they both return the first element having a key that
exceeds the provided key.
    <li> Although the keys are ordered in the <code>multimap</code>, the values for
equal keys are not ordered: they are retrieved in the order in which they were
enterd.
    </ul>
<p>
<a name="SET"></a><a name="l183"></a>
<h3>12.3.8: The `set' container</h3>
    <a name="containers/set"></a>The <a name="an1680"></a>
<code>set</code> class implements a <a name="an1681"></a>
sorted collection of values. Before <code>set</code>
containers can be used the following preprocessor directive must have been
specified: <a name="an1682"></a>

        <pre>
    #include &lt;set&gt;
</pre>
    A set is filled with values, which may be of any container-acceptable
type. Each value can be stored only once in a set.
<p>
A specific value to be inserted into a <code>set</code> can be
explicitly created: Every <code>set</code> defines a <a name="an1683"></a>
<code>value_type</code>
which may be used to <a name="an1684"></a>
create values that can be stored in the <code>set</code>. For
example, a value for a <code>set&lt;string&gt;</code> can be constructed as follows:
        <pre>
    set&lt;string&gt;::value_type setValue("Hello");
</pre>
    The <code>value_type</code> is associated with the <code>set&lt;string&gt;</code>. Anonymous
<code>value_type</code> objects are also often used. E.g.,
        <pre>
    set&lt;string&gt;::value_type("Hello");
</pre>
    Instead of using the line <code>set&lt;string&gt;::value_type(...)</code> over
and over again, a <a name="an1685"></a>
<code>typedef</code> is often used to <a name="an1686"></a>
reduce typing and to improve
<a name="an1687"></a>
legibility:
        <pre>
    typedef set&lt;string&gt;::value_type StringSetValue
</pre>
    Using this typedef, values for the <code>set&lt;string&gt;</code> may be constructed
as follows:
        <pre>
    StringSetValue("Hello");
</pre>
    Alternatively, values of the set's type may be used
immediately. In that case the value of type <code>Type</code> is implicitly
converted  to a <code>set&lt;Type&gt;::value_type</code>.
<p>
The following constructors, operators, and member functions are available
for the <code>set</code> container:
    <ul>
    <li> <a name="an1688"></a>
 Constructors:
        <ul>
        <li> A <code>set</code> may be constructed empty:
        <pre>
    set&lt;int&gt; object;
</pre>
        <li> A set may be initialized using two iterators. For example:
            <pre>
    int intarr[] = {1, 2, 3, 4, 5};

    set&lt;int&gt; object(&amp;intarr[0], &amp;intarr[5]);
</pre>
        </ul>
    Note that all values in the set must be different: it is not possible to
store the same value repeatedly when the set is constructed. If the same value
occurs repeatedly, only the first instance of the value will be entered, the
other values will be <a name="an1689"></a>
silently ignored.
<p>
Like the <a href="cplusplus12.html#MAP">map</a>, the <code>set</code> receives its own copy of the data it
contains.
        <li> A set may be initialized using a <a name="an1690"></a>
copy constructor:
        <pre>
    extern set&lt;string&gt; container;
    set&lt;string&gt; object(container);
</pre>
    <li> The <code>set</code> container only supports the standard set of operators
that are available for containers.
    <li> The <code>set</code> class has the following <a name="an1691"></a>
 member
functions:
        <ul>
        <li><a name="an1692"></a>
<code>set::iterator set::begin()</code>:<blockquote>this member
returns an <a name="an1693"></a>
iterator pointing to the first element of the set. If the set is
empty <code>set::end()</code> is returned.</blockquote>
        <li><a name="an1694"></a>
<code>set::clear()</code>:<blockquote>this member erases all elements from the set.</blockquote>
        <li><a name="an1695"></a>
<code>size_t set::count(key)</code>:<blockquote>this member returns 1 if
the provided key is available in the <code>set</code>, otherwise 0 is returned.</blockquote>
        <li><a name="an1696"></a>
<code>bool set::empty()</code>:<blockquote>this member returns <code>true</code> if
the set contains no elements.</blockquote>
        <li><a name="an1697"></a>
<code>set::iterator set::end()</code>:<blockquote>this member
returns an iterator pointing beyond the last element of the set.</blockquote>
        <li><a name="an1698"></a>
<code>pair&lt;set::iterator, set::iterator&gt; set::equal_range(key)</code>:<blockquote>this
member returns a pair of iterators, being respectively the return values of
the member functions <code>lower_bound()</code> and <code>upper_bound()</code>, introduced
below.</blockquote>
        <li><a name="an1699"></a>
<code>... set::erase()</code>:<blockquote>this member can be
used to erase a specific element or range of elements from the set:</blockquote>
            <ul>
            <li><code>bool erase(value)</code> erases the element having the given
<code>value</code> from the <code>set</code>. <code>True</code> is returned if the value was removed,
<code>false</code> if the set did not contain an element `<code>value</code>'.
            <li><code>void erase(pos)</code> erases the element pointed to by the iterator
<code>pos</code>.
            <li><code>void erase(first, beyond)</code> erases all elements
indicated by the iterator range <code>[first, beyond)</code>.
            </ul>
        <li><a name="an1700"></a>
<code>set::iterator set::find(value)</code>:<blockquote>this member returns
an iterator to the element having the given value. If the element isn't
available, <code>end()</code> is returned.</blockquote>
        <li><a name="an1701"></a>
<code>... set::insert()</code>:<blockquote>this member can be used to
insert elements into the <code>set</code>. If the element already exists, the existing
element is left untouched and the element to be inserted is ignored.  The
return value depends on the version of <code>insert()</code> that is called:</blockquote>
            <ul>
            <li><code>pair&lt;set::iterator, bool&gt; insert(keyvalue)</code> inserts
a new <code>set::value_type</code> into the set. The return value is a
<a name="an1702"></a>
<code>pair&lt;set::iterator, bool&gt;</code>.  If the returned <a name="an1703"></a>
<code>bool</code> field is <code>true</code>,
<code>value</code> was inserted into the set. The value <code>false</code> indicates that the
value that was specified was already available in the set, and
so the provided <code>value</code> was not inserted into the set.  In both cases the
<code>set::iterator</code> field points to the data element in the <code>set</code> having the
specified <code>value</code>.
            <li><code>set::iterator insert(pos, keyvalue)</code>. This way a
<code>set::value_type</code> may also be into the set. <code>pos</code> is ignored, and an
iterator to the inserted element is returned.
            <li><code>void insert(first, beyond)</code> inserts the (<code>set::value_type</code>)
elements pointed to by the <a name="an1704"></a>
iterator range <a name="an1705"></a>
<code>[first, beyond)</code> into the
set.
            </ul>
        <li><a name="an1706"></a>
<code>set::iterator set::lower_bound(key)</code>:<blockquote>this member returns an iterator pointing to the first
<code>keyvalue</code> element of which the <code>key</code> is at least equal to the specified
<code>key</code>.  If no such element exists, the function returns
<code>set::end()</code>.</blockquote>
        <li><a name="an1707"></a>
<code>set::reverse_iterator set::rbegin()</code>:<blockquote>
    <a name="an1708"></a>
 this member returns an iterator pointing to the last
element of the set.</blockquote>
        <li><a name="an1709"></a>
<code>set::reverse_iterator set::rend()</code>:<blockquote>this member
returns an iterator pointing before the first element of the set.</blockquote>
        <li><a name="an1710"></a>
<code>size_t set::size()</code>:<blockquote>this member returns the
number of elements in the set.</blockquote>
        <li><a name="an1711"></a>
<code>void set::swap(argument)</code>:<blockquote>this member can be used
to swap two sets (<code>argument</code> being the second set) that use identical data
types.</blockquote>
        <li><a name="an1712"></a>
<code>set::iterator set::upper_bound(key)</code>:<blockquote>this member returns an iterator pointing to the first
<code>keyvalue</code> element having a <code>key</code> exceeding the specified <code>key</code>.  If no
such element exists, the function returns <code>set::end()</code>.</blockquote>
        </ul>
    </ul>
<p>
<a name="MULTISET"></a><a name="l184"></a>
<h3>12.3.9: The `multiset' container</h3>
    <a name="containers/multiset"></a>Like the <code>set</code>, the <a name="an1713"></a>
<code>multiset</code> class implements a
    <a name="an1714"></a>
 sorted collection of values. Before
<code>multiset</code> containers can be used the following preprocessor directive must have
been specified: <a name="an1715"></a>

        <pre>
    #include &lt;set&gt;
</pre>
    The main difference between the <code>set</code> and the <code>multiset</code> is that the
multiset supports multiple entries of the same value, whereas the set contains
unique values.
<p>
The <code>set</code> and the <code>multiset</code> <a name="an1716"></a>
 have the same
set of member functions.  Refer to section <a href="cplusplus12.html#SET">12.3.8</a> for an overview
    <a name="an1717"></a>

    of the <code>multiset</code> member functions.  Some member functions, however,
deserve additional attention when used in the context of the <code>multiset</code>
container. These members are discussed below.
    <ul>
        <li><a name="an1718"></a>
<code>size_t set::count(value)</code>:<blockquote>this member returns
the number of entries in the multiset associated with the given
<code>value</code>.</blockquote>
        <li><a name="an1719"></a>
<code>... multiset::erase()</code>:<blockquote>this member can be
used to erase elements from the set:</blockquote>
            <ul>
            <li><code>size_t erase(value)</code> erases all elements having the
given <code>value</code>. The number of erased elements is returned.
            <li><code>void erase(pos)</code> erases the element pointed to by the iterator
<code>pos</code>. Other elements possibly having the same values are not erased.
            <li><code>void erase(first, beyond)</code> erases all elements indicated by
the iterator range <code>[first, beyond)</code>.
            </ul>
        <li><a name="an1720"></a>
<code>pair&lt;multiset::iterator, multiset::iterator&gt; multiset::equal_range(value)</code>:<blockquote>this member function returns a pair of iterators, being respectively
the return values of <code>multiset::lower_bound()</code> and
<code>multiset::upper_bound()</code>, introduced below.  The function provides a simple
means to determine all elements in the <code>multiset</code> that have the same
<code>values</code>.</blockquote>
        <li><a name="an1721"></a>
<code>multiset::iterator multiset::find(value)</code>:<blockquote>this
member returns an iterator pointing to the first element having the specified
value. If the element isn't available, <code>multiset::end()</code> is returned. The
iterator could be incremented to visit all elements having the given <code>value</code>
until it is either <code>multiset::end()</code>, or the iterator doesn't point to
`<code>value</code>' anymore.</blockquote>
        <li><a name="an1722"></a>
<code>... multiset::insert()</code>:<blockquote>this member function
normally succeeds, and so a <a name="an1723"></a>
<em>multiset::iterator</em> is returned,
instead of a <code>pair&lt;multiset::iterator, bool&gt;</code> as returned with the <code>set</code>
container. The returned iterator points to the newly added element.</blockquote>
    </ul>
    Although the functions <code>lower_bound()</code> and <code>upper_bound()</code> act
identically in the <code>set</code> and <code>multiset</code> containers, their operation in a
<code>multiset</code> deserves some additional attention. In particular note that with
the <code>multiset</code> container <code>lower_bound()</code> and <code>upper_bound()</code> produce the
same result for non-existing keys: they both return the first element having a
key exceeding the provided key.
<p>
Here is an example showing the use of various member functions of a
multiset:
    <pre>
    #include &lt;iostream&gt;
    #include &lt;set&gt;

    using namespace std;

    int main()
    {
        string
            sa[] =
            {
                "alpha",
                "echo",
                "hotel",
                "mike",
                "romeo"
            };

        multiset&lt;string&gt;
            object(&amp;sa[0], &amp;sa[5]);

        object.insert("echo");
        object.insert("echo");

        multiset&lt;string&gt;::iterator
            it = object.find("echo");

        for (; it != object.end(); ++it)
            cout &lt;&lt; *it &lt;&lt; " ";
        cout &lt;&lt; endl;

        cout &lt;&lt; "Multiset::equal_range(\"ech\")\n";
        pair
        &lt;
            multiset&lt;string&gt;::iterator,
            multiset&lt;string&gt;::iterator
        &gt;
            itpair = object.equal_range("ech");

        if (itpair.first != object.end())
            cout &lt;&lt; "lower_bound() points at " &lt;&lt; *itpair.first &lt;&lt; endl;
        for (; itpair.first != itpair.second; ++itpair.first)
            cout &lt;&lt; *itpair.first &lt;&lt; " ";

        cout &lt;&lt; endl &lt;&lt;
                object.count("ech") &lt;&lt; " occurrences of 'ech'" &lt;&lt; endl;

        cout &lt;&lt; "Multiset::equal_range(\"echo\")\n";
        itpair = object.equal_range("echo");

        for (; itpair.first != itpair.second; ++itpair.first)
            cout &lt;&lt; *itpair.first &lt;&lt; " ";

        cout &lt;&lt; endl &lt;&lt;
                object.count("echo") &lt;&lt; " occurrences of 'echo'" &lt;&lt; endl;

        cout &lt;&lt; "Multiset::equal_range(\"echoo\")\n";
        itpair = object.equal_range("echoo");

        for (; itpair.first != itpair.second; ++itpair.first)
            cout &lt;&lt; *itpair.first &lt;&lt; " ";

        cout &lt;&lt; endl &lt;&lt;
                object.count("echoo") &lt;&lt; " occurrences of 'echoo'" &lt;&lt; endl;
    }
    /*
        Generated output:

        echo echo echo hotel mike romeo
        Multiset::equal_range("ech")
        lower_bound() points at echo

        0 occurrences of 'ech'
        Multiset::equal_range("echo")
        echo echo echo
        3 occurrences of 'echo'
        Multiset::equal_range("echoo")

        0 occurrences of 'echoo'
    */
</pre>
<p>
<a name="l185"></a>
<h3>12.3.10: The `stack' container</h3>
    <a name="containers/stack"></a>The <a name="an1724"></a>
<code>stack</code> class implements a <a name="an1725"></a>
stack data structure.  Before <code>stack</code>
containers can be used the following preprocessor directive must have been
specified: <a name="an1726"></a>

        <pre>
    #include &lt;stack&gt;
</pre>
    A stack is also called a <a name="an1727"></a>
first in, last out (<a name="an1728"></a>
FILO or <a name="an1729"></a>
LIFO) data
structure, as the first item to enter the stack is the last item to leave.  A
stack is an extremely useful data structure in situations where data must
temporarily remain available. For example, programs maintain a stack to store
<a name="an1730"></a>
local variables of functions: the <a name="an1731"></a>
lifetime of these variables is
determined by the time these functions are active, contrary to
        <a name="an1732"></a>

    global (or static
        <a name="an1733"></a>

    local) variables, which live for as long as the program itself
lives. Another example is found in <a name="an1734"></a>
calculators using the
        <a name="an1735"></a>
<em>Reverse Polish Notation</em> (<a name="an1736"></a>
RPN),
    in which the operands of operators are entered in the stack, whereas
operators pop their operands off the stack and push the results of their work
back onto the stack.
<p>
As an example of the use of a stack, consider figure <a href="cplusplus12.html#StackFig">11</a>, in which
the contents of the stack is shown while the expression <code>(3 + 4) * 2</code> is
evaluated. In the RPN this expression becomes <code>3 4 + 2 *</code>, and figure
<a href="cplusplus12.html#StackFig">11</a> shows the stack contents after each <a name="an1737"></a>
<em>token</em> (i.e., the
operands and the operators) is read from the input. Notice that each operand
is indeed pushed on the stack, while each operator changes the contents of the
stack.
    <a name="StackFig"></a><p><center><img src="containers/stack/stack.gif" align="bottom" alt="Figure 11 is shown here."/><br>
Figure 11: The contents of a stack while evaluating <code>3 4 + 2 *</code>
</center><p><br>

    The <a name="an1738"></a>
expression is evaluated in five steps. The caret between the tokens
in the expressions shown on the first line of figure <a href="cplusplus12.html#StackFig">11</a> shows what
token has just been read. The next line shows the actual stack-contents, and
the final line shows the steps for referential purposes. Note that at step 2,
two numbers have been pushed on the stack. The first number (<code>3</code>) is now at
the bottom of the stack. Next, in step 3, the <code>+</code> operator is read. The
operator pops two operands (so that the stack is empty at that moment),
calculates their sum, and pushes the resulting value (<code>7</code>) on the
stack. Then, in step 4, the number <code>2</code> is read, which is dutifully pushed on
the stack again. Finally, in step 5 the final operator <code>*</code> is read, which
pops the values <code>2</code> and <code>7</code> from the stack, computes their product, and
pushes the result back on the stack. This result (<code>14</code>) could then be popped
to be displayed on some medium.
<p>
From figure <a href="cplusplus12.html#StackFig">11</a> we see that a stack has one point (the <a name="an1739"></a>
<em>top</em>)
where items can be pushed onto and popped off the stack. This top element is
the stack's only immediately visible element. It may be accessed and modified
directly.
<p>
Bearing this model of the stack in mind, let's see what we can formally do
with it, using the <code>stack</code> container. For the <code>stack</code>, the following
constructors, operators, and member functions are available:
    <ul>
    <li> <a name="an1740"></a>
 Constructors:
        <ul>
        <li> A <code>stack</code> may be constructed empty:
        <pre>
    stack&lt;string&gt; object;
</pre>
        <li> A stack may be initialized using a <a name="an1741"></a>
copy constructor:
        <pre>
    extern stack&lt;string&gt; container;
    stack&lt;string&gt; object(container);
</pre>
    </ul>
    <li> Only the basic set of container operators are supported by the
<code>stack</code>
    <li> The following <a name="an1742"></a>
member functions are available for stacks:
        <ul>
        <li><a name="an1743"></a>
<code>bool stack::empty()</code>:<blockquote>this
member returns <code>true</code> if the stack contains no elements.</blockquote>
        <li><a name="an1744"></a>
<code>void stack::push(value)</code>:<blockquote>this member places
<code>value</code> at the top of the stack, hiding the other elements from view.</blockquote>
        <li><a name="an1745"></a>
<code>void stack::pop()</code>:<blockquote>this member removes the element
at the top of the stack. Note that the popped element is <em>not</em> returned by
this member. Nothing happens if <code>pop()</code> is used with an empty stack. See
section <a href="cplusplus12.html#QUEUE">12.3.3</a> for a discussion about the reason why <code>pop()</code> has return
type <code>void</code>.</blockquote>
        <li><a name="an1746"></a>
<code>size_t stack::size()</code>:<blockquote>this
member returns the number of elements in the stack.</blockquote>
        <li><a name="an1747"></a>
<code>Type &amp;stack::top()</code>:<blockquote>this member
returns a reference to the stack's top (and only visible) element. It is the
    <a name="an1748"></a>
responsibility of the programmer to use this member only if the stack
is not empty.</blockquote>
        </ul>
    </ul>
    Note that the stack does not support iterators or a subscript
operator. The only elements that can be accessed is its top element.
  A stack can be emptied by:
    <ul>
    <li> repeatedly removing its front element;
    <li> assigning an empty stack using the same data type to it;
    <li> having its destructor called.
    </ul>
<p>
<a name="HASHMAP"></a><a name="l186"></a>
<h3>12.3.11: The `hash_map' and other hashing-based containers</h3>
    <a name="containers/hashmap"></a>The map is a sorted data structure. The keys in maps are sorted using the
<a name="an1749"></a>
<code>operator&lt;()</code> of the key's <a name="an1750"></a>
data type. Generally, this is not the fastest
way to either store or retrieve data.  The main benefit of sorting is that a
listing of sorted keys appeals more to humans than an unsorted list.  However,
a by far faster method to store and retrieve data is to use <a name="an1751"></a>
<em>hashing</em>.
<p>
Hashing uses a function (called the <a name="an1752"></a>
<em>hash function</em>) to compute an
(unsigned) number from the key, which number is thereupon used as an index in
the table in which the keys are stored. Retrieval of a key is as simple as
computing the <a name="an1753"></a>
hash value of the provided key, and looking in the table at
the computed index location: if the key is present, it is stored in the table,
and its value can be returned. If it's not present, the key is not stored.
<p>
Collisions <a name="an1754"></a>
 occur when a computed index position is already
occupied by another element. For these situations the abstract containers have
solutions available, but that topic is beyond the subject of this chapter.
<p>
The <a name="an1755"></a>
Gnu <a name="an1756"></a>
g++ compiler supports the <em>hash_(multi)map</em> and
<code>hash_(multi)set</code> containers. Below the <a name="an1757"></a>
<code>hash_map</code> container is
discussed.  Other containers using hashing (<a name="an1758"></a>
<code>hash_multimap</code>,
<a name="an1759"></a>
<code>hash_set</code> and <a name="an1760"></a>
<code>hash_multiset</code>) operate correspondingly.
<p>
Concentrating on the <code>hash_map</code>, its constructor needs a <a name="an1761"></a>
<em>key type</em>, a
<a name="an1762"></a>
value type, an object creating a hash value for the key, and an object
comparing two keys for equality.  Hash functions are available for
    <a name="an1763"></a>
<code>char const *</code> keys, and for all the
    <a name="an1764"></a>
scalar numerical types <code>char, short, int</code> etc.. If another data type
is used, a hash function and an equality test must be implemented,
possibly using <a name="an1765"></a>
 <em>function objects</em> (see section
<a href="cplusplus09.html#FUNOBJ">9.10</a>). For both situations examples are given below.
<p>
The class implementing the hash function could be called <code>hash</code>.  Its
<a name="an1766"></a>
function call operator (<a name="an1767"></a>
<code>operator()()</code>) returns the hash value of the key
that is passed as its argument.
<p>
A <em>generic algorithm</em> (see chapter <a href="cplusplus17.html#STL">17</a>) exists for the test of equality
(i.e., <code>equal_to()</code>), which can be used if the key's data type supports the
equality operator. Alternatively, a specialized <a name="an1768"></a>
function object could be
constructed here, supporting the equality test of two keys. Again, both
situations are illustrated below.
<p>
The <code>hash_map</code> class implements an <a name="an1769"></a>
associative array in which the key is
stored according to some hashing scheme. Before <code>hash_map</code> containers can be
used the following preprocessor directive must have been specified:
    <a name="an1770"></a>

        <pre>
    #include &lt;ext/hash_map&gt;
</pre>
    The <code>hash_(multi)map</code> is not yet part of the <a name="an1771"></a>
ANSI/ISO standard.  Once
this container becomes part of the standard, it is likely that the <code>ext/</code>
prefix in the <code>#include</code> preprocessor directive can be removed. Note that
starting with the
    <a name="an1772"></a>
Gnu <a name="an1773"></a>
<code>g++</code> <a name="an1774"></a>
compiler version 3.2 the <a name="an1775"></a>
<code>__gnu_cxx</code> namespace is used
for symbols defined in the <code>ext/</code> header files. See also section
<a href="cplusplus02.html#WHATSNEW">2.1</a>.
<p>
Constructors, operators and member functions available for the <code>map</code> are
also available for the <code>hash_map</code>. The <code>map</code> and <code>hash_map</code> support
the same set of operators and member functions. However, the
<a name="an1776"></a>
<em>efficiency</em> of a <code>hash_map</code> in terms of speed should greatly exceed the
efficiency of the <code>map</code>. Comparable conclusions may be drawn for the
<code>hash_set</code>, <code>hash_multimap</code> and the <code>hash_multiset</code>.
<p>
Compared to the <code>map</code> container, the <code>hash_map</code> has an additional
constructor:
        <pre>
        hash_map&lt;...&gt; hash(n);
</pre>
    where <code>n</code> is a <code>size_t</code> value, may be used to construct a
<code>hash_map</code> consisting of an initial number of at least <code>n</code> empty slots to
put key/value combinations in. This number is automatically extended when
needed.
<p>
The hashed key type is almost always text. So, a <code>hash_map</code> in which the
key's data type is either <code>char const *</code> or a <code>string</code> occurs most often.
If the following <a name="an1777"></a>
header file is installed in the <strong>C++</strong> compiler's
<a name="an1778"></a>
<code>INCLUDE path</code> as the file <a name="an1779"></a>
<code>hashclasses.h</code>, sources may specify the
following preprocessor directive to make a set of classes available that can
be used to instantiate <a name="an1780"></a>
 a hash table
    <a name="an1781"></a>

        <pre>
    #include &lt;hashclasses.h&gt;
</pre>
    Otherwise, sources must specify the following preprocessor directive:
        <pre>
    #include &lt;ext/hash_map&gt;
</pre>
        <pre>
#ifndef _INCLUDED_HASHCLASSES_H_
#define _INCLUDED_HASHCLASSES_H_

#include &lt;string&gt;
#include &lt;cctype&gt;

/*
    Note that with the Gnu g++ compiler 3.2 (and beyond?) the ext/ header
    uses the __gnu_cxx namespace for symbols defined in these header files.

    When using compilers before version 3.2, do:
        #define __gnu_cxx   std
    before including this file to circumvent problems that may occur
    because of these namespace conventions which were not yet used in versions
    before 3.2.

*/

#include &lt;ext/hash_map&gt;
#include &lt;algorithm&gt;

/*
    This file is copyright (c) GPL, 2001-2004
    ==========================================
    august 2004: redundant include guards removed

    october 2002:   provisions for using the hashclasses with the g++ 3.2
                compiler were incorporated.

    april 2002: namespace FBB introduced
                abbreviated class templates defined,
                see the END of this comment section for examples of how
                to use these abbreviations.

    jan 2002:   redundant include guards added,
                required header files adapted,
                for_each() rather than transform() used

    With hash_maps using char const * for the keys:
                         ============

    * Use `HashCharPtr' as 3rd template argument for case-sensitive keys
    * Use `HashCaseCharPtr' as 3rd template argument for case-insensitive
      keys

    * Use `EqualCharPtr' as 4th template argument for case-sensitive keys
    * Use `EqualCaseCharPtr' as 4th template argument for case-insensitive
      keys


    With hash_maps using std::string for the keys:
                         ===========

    * Use `HashString' as 3rd template argument for case-sensitive keys
    * Use `HashCaseString' as 3rd template argument for case-insensitive keys

    * OMIT the 4th template argument for case-sensitive keys
    * Use `EqualCaseString' as 4th template argument for case-insensitive
        keys


    Examples, using int as the value type. Any other type can be used instead
              for the value type:

                                    // key is char const *, case sensitive
        __gnu_cxx::hash_map&lt;char const *, int, FBB::HashCharPtr,
                            FBB::EqualCharPtr &gt;
            hashtab;

                                    // key is char const *, case insensitive
        __gnu_cxx::hash_map&lt;char const *, int, FBB::HashCaseCharPtr,
                                         FBB::EqualCaseCharPtr &gt;
            hashtab;

                                    // key is std::string, case sensitive
        __gnu_cxx::hash_map&lt;std::string, int, FBB::HashString&gt;
            hashtab;

                                    // key is std::string, case insensitive
        __gnu_cxx::hash_map&lt;std::string, int, FBB::HashCaseString,
                                        FBB::EqualCaseString&gt;
            hashtab;

    Instead of the above full typedeclarations, the following shortcuts should
    work as well:

        FBB::CharPtrHash&lt;int&gt;       // key is char const *, case sensitive
            hashtab;

        FBB::CharCasePtrHash&lt;int&gt;   // key is char const *, case insensitive
            hashtab;

        FBB::StringHash&lt;int&gt;        // key is std::string, case sensitive
            hashtab;

        FBB::StringCaseHash&lt;int&gt;    // key is std::string, case insensitive
            hashtab;

    With these template types iterators and other map-members are also
    available. E.g.,

    --------------------------------------------------------------------------
    extern FBB::StringHash&lt;int&gt; dh;

    for (FBB::StringHash&lt;int&gt;::iterator it = dh.begin(); it != dh.end(); it++)
        std::cout &lt;&lt; it-&gt;first &lt;&lt; " - " &lt;&lt; it-&gt;second &lt;&lt; std::endl;
    --------------------------------------------------------------------------

    Feb. 2001 - April 2002
    Frank B. Brokken (f.b.brokken@rug.nl)
*/

namespace FBB
{

    class HashCharPtr
    {
        public:
            size_t operator()(char const *str) const
            {
                return __gnu_cxx::hash&lt;char const *&gt;()(str);
            }
    };

    class EqualCharPtr
    {
        public:
            bool operator()(char const *x, char const *y) const
            {
                return !strcmp(x, y);
            }
    };

    class HashCaseCharPtr
    {
        public:
            size_t operator()(char const *str) const
            {
                std::string s = str;
                for_each(s.begin(), s.end(), *this);
                return __gnu_cxx::hash&lt;char const *&gt;()(s.c_str());
            }
            void operator()(char &amp;c) const
            {
                c = tolower(c);
            }
    };

    class EqualCaseCharPtr
    {
        public:
            bool operator()(char const *x, char const *y) const
            {
                return !strcasecmp(x, y);
            }
    };

    class HashString
    {
        public:
            size_t operator()(std::string const &amp;str) const
            {
                return __gnu_cxx::hash&lt;char const *&gt;()(str.c_str());
            }
    };

    class HashCaseString: public HashCaseCharPtr
    {
        public:
            size_t operator()(std::string const &amp;str) const
            {
                return HashCaseCharPtr::operator()(str.c_str());
            }
    };

    class EqualCaseString
    {
        public:
            bool operator()(std::string const &amp;s1, std::string const &amp;s2) const
            {
                return !strcasecmp(s1.c_str(), s2.c_str());
            }
    };


    template&lt;typename Value&gt;
    class CharPtrHash: public
        __gnu_cxx::hash_map&lt;char const *, Value, HashCharPtr, EqualCharPtr &gt;
    {
        public:
            CharPtrHash()
            {}
            template &lt;typename InputIterator&gt;
            CharPtrHash(InputIterator first, InputIterator beyond)
            :
                __gnu_cxx::hash_map&lt;char const *, Value, HashCharPtr,
                                    EqualCharPtr&gt;(first, beyond)
            {}
    };

    template&lt;typename Value&gt;
    class CharCasePtrHash: public
        __gnu_cxx::hash_map&lt;char const *, Value, HashCaseCharPtr,
                                                 EqualCaseCharPtr &gt;
    {
        public:
            CharCasePtrHash()
            {}
            template &lt;typename InputIterator&gt;
            CharCasePtrHash(InputIterator first, InputIterator beyond)
            :
                __gnu_cxx::hash_map&lt;char const *, Value,
                            HashCaseCharPtr, EqualCaseCharPtr&gt;
                            (first, beyond)
            {}
    };

    template&lt;typename Value&gt;
    class StringHash: public __gnu_cxx::hash_map&lt;std::string, Value,
                                                 HashString&gt;
    {
        public:
            StringHash()
            {}
            template &lt;typename InputIterator&gt;
            StringHash(InputIterator first, InputIterator beyond)
            :
                __gnu_cxx::hash_map&lt;std::string, Value, HashString&gt;
                             (first, beyond)
            {}
    };


    template&lt;typename Value&gt;
    class StringCaseHash: public
            __gnu_cxx::hash_map&lt;std::string, int, HashCaseString,
                                EqualCaseString&gt;
    {
        public:
            StringCaseHash()
            {}
            template &lt;typename InputIterator&gt;
            StringCaseHash(InputIterator first, InputIterator beyond)
            :
                __gnu_cxx::hash_map&lt;std::string,
                            int, HashCaseString,
                            EqualCaseString&gt;(first, beyond)
            {}
    };

    template&lt;typename Key, typename Value&gt;
    class Hash: public
            __gnu_cxx::hash_map&lt;Key, Value,
                        __gnu_cxx::hash&lt;Key&gt;(),
                        equal&lt;Key&gt;())
    {};

}
#endif
</pre>
    The following program defines a hash_map containing the names of the
months of the year and the number of days these months (usually) have. Then,
using the subscript operator the days in several months are displayed. The
equality operator used the generic algorithm <code>equal_to&lt;string&gt;</code>, which is
the default fourth argument of the <code>hash_map</code> constructor:
        <pre>
    #include &lt;iostream&gt;
        // the following header file must be available in the compiler's
        // INCLUDE path:
    #include &lt;hashclasses.h&gt;
    using namespace std;
    using namespace FBB;

    int main()
    {
        __gnu_cxx::hash_map&lt;string, int, HashString &gt; months;
        // Alternatively, using the classes defined in hashclasses.h,
        // the following definitions could have been used:
        //      CharPtrHash&lt;int&gt; months;
        // or:
        //      StringHash&lt;int&gt; months;

        months["january"] = 31;
        months["february"] = 28;
        months["march"] = 31;
        months["april"] = 30;
        months["may"] = 31;
        months["june"] = 30;
        months["july"] = 31;
        months["august"] = 31;
        months["september"] = 30;
        months["october"] = 31;
        months["november"] = 30;
        months["december"] = 31;

        cout &lt;&lt; "september -&gt; " &lt;&lt; months["september"] &lt;&lt; endl &lt;&lt;
                "april     -&gt; " &lt;&lt; months["april"] &lt;&lt; endl &lt;&lt;
                "june      -&gt; " &lt;&lt; months["june"] &lt;&lt; endl &lt;&lt;
                "november  -&gt; " &lt;&lt; months["november"] &lt;&lt; endl;
    }
    /*
        Generated output:
    september -&gt; 30
    april     -&gt; 30
    june      -&gt; 30
    november  -&gt; 30
    */
</pre>
<p>
The <code>hash_multimap, hash_set</code> and <code>hash_multiset</code> containers are used
analogously. For these containers the <code>equal</code> and <code>hash</code> classes must also
be defined. The <code>hash_multimap</code> also requires the <code>hash_map</code> header file.
<p>
Before the <code>hash_set</code> and <code>hash_multiset</code> containers can be used the
following preprocessor directive must have been specified:
    <a name="an1782"></a>

        <pre>
    #include &lt;ext/hash_set&gt;
</pre>
<p>
<a name="COMPLEX"></a><a name="l187"></a>
<h2>12.4: The `complex' container</h2>
<a name="containers/complex"></a>The <a name="an1783"></a>
<code>complex</code> container is a specialized container in that it defines
operations that can be performed on <a name="an1784"></a>
complex numbers, given possible
numerical real and imaginary data types.
<p>
Before <code>complex</code> containers can be used the following preprocessor directive
must have been specified: <a name="an1785"></a>

        <pre>
    #include &lt;complex&gt;
</pre>
    The <code>complex</code> container can be used to define complex numbers,
consisting of two parts, representing the real and imaginary parts of a
complex number.
<p>
While initializing (or assigning) a complex variable, the <a name="an1786"></a>
imaginary part
may be left out of the initialization or assignment, in which case this part
is <code>0</code> (zero). By default, both parts are zero.
<p>
When complex numbers are defined, the type definition requires the
specification of the datatype of the real and imaginary parts. E.g.,
        <pre>
    complex&lt;double&gt;
    complex&lt;int&gt;
    complex&lt;float&gt;
</pre>
    Note that the real and imaginary parts of complex numbers have the same
datatypes.
<p>
Below it is silently assumed that the used <code>complex</code> type is
<code>complex&lt;double&gt;</code>. Given this assumption, complex numbers may be initialized
as follows:
    <ul>
    <li><code>target</code>:   A default initialization: real and imaginary parts are 0.
    <li><code>target(1)</code>: The <a name="an1787"></a>
real part is 1, imaginary part is 0
    <li><code>target(0, 3.5)</code>: The real part is 0, imaginary part is 3.5
    <li><code>target(source)</code>: <code>target</code> is initialized with the values of
<code>source</code>.
    </ul>
    Anonymous complex values may also be used. In the following example two
<a name="an1788"></a>
anonymous complex values are pushed on a stack of complex numbers, to be
popped again thereafter:
        <pre>
    #include &lt;iostream&gt;
    #include &lt;complex&gt;
    #include &lt;stack&gt;

    using namespace std;

    int main()
    {
        stack&lt;complex&lt;double&gt; &gt;
            cstack;

        cstack.push(complex&lt;double&gt;(3.14, 2.71));
        cstack.push(complex&lt;double&gt;(-3.14, -2.71));

        while (cstack.size())
        {
            cout &lt;&lt; cstack.top().real() &lt;&lt; ", " &lt;&lt;
                    cstack.top().imag() &lt;&lt; "i" &lt;&lt; endl;
            cstack.pop();
        }
    }
    /*
        Generated output:
    -3.14, -2.71i
    3.14, 2.71i
    */
</pre>
    Note the required <a name="an1789"></a>
extra blank space between the two closing
    <a name="an1790"></a>
pointed arrows in the <a name="an1791"></a>
type specification of <code>cstack</code>.
<p>
The following member functions and operators are defined for complex
numbers (below, <code>value</code> may be either a primitve <a name="an1792"></a>
scalar type or a
<code>complex</code> object):
    <ul>
        <li> Apart from the standard container operators, the following
operators are supported from the <code>complex</code> container.
        <ul>
        <li><a name="an1793"></a>
<code>complex complex::operator+(value)</code>:<blockquote> this
member returns the sum of the current <code>complex</code> container and <code>value</code>.</blockquote>
        <li><a name="an1794"></a>
<code>complex complex::operator-(value)</code>:<blockquote> this
member returns the difference between the current <code>complex</code> container and
<code>value</code>.</blockquote>
        <li><a name="an1795"></a>
<code>complex complex::operator*(value)</code>:<blockquote> this
member returns the product of the current <code>complex</code> container and
<code>value</code>.</blockquote>
        <li><a name="an1796"></a>
<code>complex complex::operator/(value)</code>:<blockquote> this
member returns the quotient of the current <code>complex</code> container and
<code>value</code>.</blockquote>
        <li><a name="an1797"></a>
<code>complex complex::operator+=(value)</code>:<blockquote> this
member adds <code>value</code> to the current <code>complex</code> container, returning the
new value.</blockquote>
        <li><a name="an1798"></a>
<code>complex complex::operator-=(value)</code>:<blockquote>
this member subtracts <code>value</code> from the current <code>complex</code> container,
returning the new value.</blockquote>
        <li><a name="an1799"></a>
<code>complex complex::operator*=(value)</code>:<blockquote> this
member multiplies the current <code>complex</code> container by <code>value</code>, returning
the new value</blockquote>
        <li><a name="an1800"></a>
<code>complex complex::operator/=(value)</code>:<blockquote> this
member divides the current <code>complex</code> container by <code>value</code>, returning the
new value.</blockquote>
        </ul>
        <li><a name="an1801"></a>
<code>Type complex::real()</code>:<blockquote>this member returns the <a name="an1802"></a>
real part of a
complex number.</blockquote>
        <li><a name="an1803"></a>
<code>Type complex::imag()</code>:<blockquote>this member returns the <a name="an1804"></a>
imaginary part
of a complex number.</blockquote>
        <li> Several <a name="an1805"></a>
mathematical functions are available for the
<code>complex</code> container, such as <a name="an1806"></a>
<code>abs()</code>, <a name="an1807"></a>
<code>arg()</code>, <a name="an1808"></a>
<code>conj()</code>, <a name="an1809"></a>
<code>cos()</code>,
<a name="an1810"></a>
<code>cosh()</code>, <a name="an1811"></a>
<code>exp()</code>, <a name="an1812"></a>
<code>log()</code>, <a name="an1813"></a>
<code>norm()</code>, <a name="an1814"></a>
<code>polar()</code>, <a name="an1815"></a>
<code>pow()</code>,
<a name="an1816"></a>
<code>sin()</code>, <a name="an1817"></a>
<code>sinh()</code> and <a name="an1818"></a>
<code>sqrt()</code>. These functions are normal functions,
not member functions, accepting complex numbers as their arguments. For
example,
        <pre>
    abs(complex&lt;double&gt;(3, -5));
    pow(target, complex&lt;int&gt;(2, 3));
</pre>
        <li> Complex numbers may be <a name="an1819"></a>
 extracted from
<code>istream</code> objects and inserted <a name="an1820"></a>
 into <code>ostream</code> objects. The
insertion results in an <a name="an1821"></a>
ordered pair <code>(x, y)</code>, in which <code>x</code> represents
the real part and <code>y</code> the imaginary part of the complex number. The same
form may also be used when extracting a complex number from an <code>istream</code>
object. However, simpler forms are also allowed. E.g., <code>1.2345</code>: only the
real part, the imaginary part will be set to 0; <code>(1.2345)</code>: the same value.
    </ul>
<p>

<hr>
<ul>
    <li> <a href="cplusplus.html">Table of Contents</a>
    <li> <a href="cplusplus11.html">Previous Chapter</a>
    <li> <a href="cplusplus13.html">Next Chapter</a>
</ul>
<hr>
</body>
</html>
